The problem
Given coin values coins (as many of each as you like) and an amount, return the number of different combinations of coins that make up amount. The order of coins does not matter: 1 + 2 and 2 + 1 are one combination.
Examples
- Input
amount = 5, coins = [1, 2, 5]
- Output
4
- Input
amount = 3, coins = [2]
- Output
0
- Input
amount = 10, coins = [10]
- Output
1
Constraints
- 1 ≤ coins.length ≤ 300
- 1 ≤ coins[i] ≤ 5000, all different
- 0 ≤ amount ≤ 5000
- The answer fits in a 32-bit signed integer.
The idea
Counting orderings would be easy and wrong. To count each combination once, decide the coins one kind at a time: first how many 1s, then how many 2s, and so on. ways[x] counts combinations of x using only the kinds considered so far.
Adding a kind c: combinations of x now either use no c (the old ways[x]) or at least one, leaving x − c made with kinds up to and including c (the new ways[x − c]). Updating x upwards reads the new value, so c can repeat. Only the final answer is promised to fit in 32 bits; the solutions add modulo 2³² where the language would otherwise overflow, which leaves that final answer exact.
- Time
- O(amount × number of coins)
- Space
- O(amount)
Solution · every language run against every case
class Solution: def change(self, amount: int, coins: List[int]) -> int: # ways[x]: combinations making x from the coins taken so far. Taking coins one kind at a # time counts each combination once, in one order — 1 + 2 and 2 + 1 are not both counted. ways = [1] + [0] * amount for c in coins: for x in range(c, amount + 1): ways[x] += ways[x - c] # combinations for x that use at least one more c return ways[amount]