Problem overview
The function change(amount, coins) receives a target sum and a list of distinct coin values. Each value can be used as many times as you like. It returns how many different combinations of coins add up to exactly amount, or 0 if none does. A combination counts how many coins of each value it uses, not their order, so 2 + 2 + 1 and 1 + 2 + 2 are the same combination.
For amount = 5 and coins = [1, 2, 5] the answer is 4: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 and 1 + 1 + 1 + 1 + 1. For amount = 3 and coins = [2] the answer is 0, since coins of 2 only make even sums. When amount is 0 the answer is 1: the combination of no coins at all.
Approach: count combinations for every smaller sum
Listing every combination does not scale. With amount up to 5000 and up to 300 coin values, the number of combinations can be astronomically large, and it can't be produced one by one. The answer has to be counted, and counting works because the problem repeats itself: a combination for a sum a that ends with a coin of value c is a combination for a - c plus one more coin c.
So build a list ways where ways[a] is the number of combinations that make the sum a, for every a from 0 to amount. It starts with ways[0] = 1 (no coins) and zeros everywhere else, and the answer is ways[amount]. The note asks for O(n · amount) time and O(amount) space, where n is the number of coins, and this list is exactly that size.
Why the coins are the outer loop
The order of the two loops decides what gets counted. With the coins in the outer loop, a coin is added to the counts only after all the earlier coins have been processed, so each combination is built in one fixed order: first its coins of the first value, then those of the second, and so on. Every combination is reached by exactly one path and counted once. 1 + 3 is counted; 3 + 1 never is.
With the sums in the outer loop and the coins inside, any coin can be the last one added to any sum, so 1 + 3 and 3 + 1 are both counted. That counts ordered sequences, not combinations. For amount = 4 and coins = [1, 2, 3], the correct loop order gives 4 and the swapped one gives 7.
Here is ways after each coin for amount = 5 and coins = [1, 2, 5]:
after coin 1: [1, 1, 1, 1, 1, 1]
after coin 2: [1, 1, 2, 2, 3, 3]
after coin 5: [1, 1, 2, 2, 3, 4]
With only the coin 1, every sum has one combination. Adding the coin 2 gives sum 4 three ways (1+1+1+1, 2+1+1, 2+2), and adding the coin 5 adds one more way to make 5. The last entry, 4, is the answer.
Step by step
- Create
waysas[0] * (amount + 1). Before any coin is used, no sum above 0 can be made, so every count starts at 0. The list has one slot for each sum from 0 toamount. - Set
ways[0] = 1. The sum 0 has one combination, the empty one. Every other combination grows from it: one coin added to no coins makes a sum equal to the coin's value. - Loop over
coinswith a variablecoin. This is the outer loop, which is what turns the counts into combinations rather than orders. - Loop
aoverrange(coin, amount + 1). A sum smaller than the coin can't contain it, so the loop starts atcoin. It goes upward, which letsways[a - coin]already include this coin, so one value can be used again and again.rangestops before its end, soamountis the last sum. Whencoinis bigger thanamountthe range is empty and the coin is skipped. - Add
ways[a - coin]toways[a]. This is the key line. Each combination fora - coin, plus one more of this coin, is a combination fora. - Return
ways[amount]. Whenamountis 0 neither loop does any work and the function returnsways[0], which is 1.
The solution in Python
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
ways = [0] * (amount + 1)
ways[0] = 1
for coin in coins:
for a in range(coin, amount + 1):
ways[a] += ways[a - coin]
return ways[amount]
Some Python details:
[0] * (amount + 1)builds a list ofamount + 1zeros. This is safe for numbers because integers are immutable: each slot holds its own value once you assign to it withways[a] += .... (Repeating a list of lists this way would be a different story, because the rows would be one shared object.)ways[a] += ways[a - coin]reads the right side first and then stores the sum. Becauseagoes up,ways[a - coin]was updated earlier in this same pass, and that is what allows repeated use of one coin.- Big counts need no care. Python integers don't overflow. The constraints promise that the answers fit in 32 bits anyway; for a larger input the code would still be correct.
- The type hint
List[int]is only documentation. It doesn't check or convert anything at run time.
Complexity
Each of the n coins sweeps over at most amount + 1 sums, with a constant amount of work per sum, so the time is O(n · amount). The list ways has amount + 1 entries, so the space is O(amount). The result for the largest amount is built entirely from the counts of smaller sums, so nothing is computed twice.
Edge cases and common mistakes
- Swapping the loops. The most common bug. The counts look plausible but are too big, since they count orders. For
amount = 5andcoins = [1, 2, 5]the swapped loops return 9 instead of 4. - Forgetting
ways[0] = 1. Every count stays 0 and the function always returns 0. - Amount 0. The answer is 1, not 0. With a single coin of 7,
change(0, [7])returns 1. - A coin larger than the amount.
range(coin, amount + 1)is empty, so the coin changes nothing.change(10, [10])returns 1, and a coin of 10 with amount 5 contributes nothing. - Starting the inner loop at 0.
ways[a - coin]would then use a negative index, which in Python reads from the end of the list instead of failing. - Going downward in the inner loop. That would let each coin be used at most once, which solves a different problem.
Testing
These calls, made on a Solution object, give:
change(5, [1, 2, 5]) -> 4
change(3, [2]) -> 0
change(4, [1, 2, 3]) -> 4
change(0, [7]) -> 1
change(10, [10]) -> 1
change(5000, [1, 2, 5]) -> 1252001
