Description
Count combinations of unlimited coins that total amount. Coin denominations are distinct positive integers. Order does not distinguish combinations; amount zero has one empty combination. Assume the result fits a signed 32-bit integer.
Solution
def change(amount, coins):
ways = [0] * (amount + 1)
ways[0] = 1
for coin in coins:
for total in range(coin, amount + 1):
ways[total] += ways[total - coin]
return ways[amount]Examples
Example 1
- Input
[5,[1,2,5]]- Output
4
The four combinations are 5; 2+2+1; 2+1+1+1; and five 1s.
Example 2
- Input
[3,[2]]- Output
0
An odd amount cannot use only 2s.
Example 3
- Input
[0,[1,2]]- Output
1
Choosing no coins is one combination.
Approach
Initialize ways[0] to one. Process coin denominations outside and increasing amounts inside, adding ways[amount - coin]. This counts each unordered combination once while allowing coin reuse.
Time & space
O(c A) time and O(A) auxiliary space, where c is denomination count and A is the target amount.