Lottery Coupons or Coin Change

MediumPython

Problem

TraceLink Product Track may evaluate rule sets containing reusable numeric values. Given a collection of coin or coupon denominations and a target value, return every unique combination whose values sum to the target.

Each denomination may be selected unlimited times. The input may contain duplicate denomination values, but duplicate combinations must appear only once. Within every combination, values must be in nondecreasing order. Return the combinations in lexicographic order, where the first differing value determines ordering. Return an empty list when no combination exists.

Formal Specification

Implement find_combinations(denominations, target).

denominations is a list of positive integers.
target is a positive integer.
Return a list of lists of integers.
Each returned list must sum to target.
The same denomination can be used repeatedly.
A combination's ordering does not matter mathematically, so [2, 3] and [3, 2] are the same combination.

Constraints

1 <= len(denominations) <= 20
1 <= denominations[i] <= 100
Duplicate denomination values may occur
1 <= target <= 300
Every denomination is positive

Function Signature

def find_combinations(denominations, target):

Formal Specification

Implement find_combinations(denominations, target).

denominations is a list of positive integers.
target is a positive integer.
Return a list of lists of integers.
Each returned list must sum to target.
The same denomination can be used repeatedly.
A combination's ordering does not matter mathematically, so [2, 3] and [3, 2] are the same combination.