Problem overview
The function change receives a target amount and a vector coins of distinct coin values. It returns how many different combinations of coins add up to exactly amount, using each value as many times as you like. 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 one. If nothing adds up, the answer is 0, and for amount = 0 the answer is 1: the combination of no coins at all.
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] it is 0, because coins of 2 only make even sums.
Approach: count sums, one coin at a time
Listing every combination is hopeless: the number of combinations grows so fast that a few dozen coins can make more than a billion ways to reach 5000. The statement asks for O(n * amount) time, where n is the number of coins, so the answer has to be counted, not listed.
Let ways[a] be the number of combinations that make the sum a, for every a from 0 to amount. The table starts with ways[0] = 1 (the empty combination) and zeros elsewhere. Then the coins are added one at a time. When a coin is added, every combination for a - coin, plus one more of this coin, is a combination for a, so ways[a] grows by ways[a - coin].
Two details make this count combinations and not something else:
- The sums go upward. When
ais processed,ways[a - coin]has already been updated for this coin, so it already includes combinations that use the coin once or more. That lets one coin value be used again and again. - The coins are the outer loop. While a coin is being added, the counts only use the coins before it. So every combination is built in one fixed order: all its coins of the first value, then of the second, and so on. It is counted exactly once.
1 + 3is built, and3 + 1never is.
Swapping the loops, with the sums outside and the coins inside, lets any coin be the last one added to any sum, so 1 + 3 and 3 + 1 are both counted. That counts orders, not combinations: for amount = 4 and coins = [1, 2, 3] it gives 7 instead of 4.
Here is the table for amount = 5 and coins = [1, 2, 5], one row after each coin, for sums 0 to 5:
start: 1 0 0 0 0 0
coin 1: 1 1 1 1 1 1
coin 2: 1 1 2 2 3 3
coin 5: 1 1 2 2 3 4The last entry, 4, is the answer. After coin 1, every sum has one way: all ones. Coin 2 adds the combinations with at least one 2, and coin 5 adds the single combination 5 to the last entry.
Step by step
- Create
waysas avector<int>of sizeamount + 1with every element 0. The constructor takes the size first and then the value of every element. Before any coin is added, no sum above 0 can be made. - Set
ways[0]to 1. The sum 0 has exactly one combination, no coins. Every other combination grows from it. - Loop over
coinswith a range-basedforand anint coin. This is the outer loop, which makes the counts combinations. - Loop
afromcoinup toamount. A sum smaller than the coin cannot contain it. Going up lets a smaller sum already include this coin. - Add
ways[a - coin]toways[a]with+=. This is the key line, and it reuses the counts for smaller sums: that is the dynamic programming. - Return
ways[amount]after the outer loop. Foramount = 0the inner loops never run and this returnsways[0], which is 1.
The solution in C++
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> ways(amount + 1, 0);
ways[0] = 1;
for (int coin : coins) {
for (int a = coin; a <= amount; a++) {
ways[a] += ways[a - coin];
}
}
return ways[amount];
}
};
The C++ details worth a closer look:
vector<int> ways(amount + 1, 0)is the constructor with a size and a fill value. Without the second argument the elements would be value-initialized to 0 as well, but writing the 0 makes the intent clear.for (int coin : coins)copies each coin into a localint, which is cheap for anint. The parametercoinsis avector<int>&, a reference, so the whole vector is not copied when the function is called.- Counts and
int. The counts are plainintvalues. The statement promises that the answer, and the number of combinations for every smaller amount, fits in 32 bits, so+=never overflows. Signed overflow would be undefined behaviour in C++, not a silent wrap. - Coin order doesn't matter. With
coins = [3, 1, 2]andamount = 4, the function also returns 4. Any order gives the same set of combinations, only built in a different sequence.
Complexity
Time: O(n * amount). Each of the n coins runs the inner loop over at most amount + 1 sums, with one addition per step.
Space: O(amount). The only extra memory is the ways vector with amount + 1 entries. There is no two-dimensional table: each coin updates the same vector in place.
Edge cases and common mistakes
- Amount 0. The answer is 1, not 0. For
amount = 0andcoins = [7]the function returns 1. - Impossible amounts.
amount = 3withcoins = [2]returns 0, because the entries for odd sums are never touched. - A coin larger than the amount. The inner loop starts above
amountand does nothing, so the coin is ignored. - Swapped loops. Putting the sums in the outer loop counts orders. For
amount = 4andcoins = [1, 2, 3]it returns 7 instead of 4. - Going down in the inner loop. Looping
afromamountdown tocoinreads values that do not yet include the current coin, so each coin is used at most once. That solves a different problem. - Forgetting
ways[0] = 1. Every entry stays 0 and the function returns 0 for every input.
Testing
amount = 5,coins = [1, 2, 5]gives4.amount = 3,coins = [2]gives0.amount = 4,coins = [1, 2, 3]gives4.amount = 0,coins = [7]gives1.amount = 10,coins = [5]gives1.
