Problem overview
The method change(int amount, int[] coins) receives a target sum and an array of different coin values. It returns how many combinations of coins add up to exactly amount, or 0 if none do. Each coin value can be used any number of times. 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.
With 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. With amount = 3 and coins = [2] the answer is 0, because a 2-coin only makes even sums. With amount = 0 the answer is 1: the combination of no coins at all.
Approach: count sums, one coin at a time
Listing every combination is hopeless for large inputs: a few dozen coins can make over a billion combinations of 5000. Counting is enough, and the counts for small sums can be reused for big ones.
Let ways[a] be the number of combinations that make the sum a, for every a from 0 to amount. Start with ways[0] = 1 (no coins) and every other entry at 0. The answer is ways[amount].
Now add the coins one at a time. When a coin is added, every combination for the sum a - coin, plus one more of that coin, is a combination for a. So ways[a] += ways[a - coin].
The order of the two loops decides what is counted. With the coins in the outer loop, each combination is built in one fixed order: all its coins of the first value, then all of the second, and so on. It is therefore counted exactly once, and 1 + 3 is counted but 3 + 1 never is. If the sums were outside and the coins inside, any coin could be the last one added to any sum, and 1 + 3 and 3 + 1 would both be counted. That counts orders, not combinations: for amount = 4 and coins = [1, 2, 3] the combinations number 4, and counting orders gives 7.
The inner loop goes upward from coin. Going up means ways[a - coin] may already include the current coin, which is what lets one coin value be used again and again.
The table after each coin
For amount = 5 and coins = [1, 2, 5], the array ways (indexes 0 to 5) looks like this after each coin:
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]
After the coin 1, each sum has one combination: all ones. The coin 2 adds the combinations that use 2s, so the sum 4 now has three (1+1+1+1, 2+1+1, 2+2). The coin 5 adds one more way to make 5, the single coin. The last entry is 4, the answer.
For amount = 4 and coins = [1, 2, 3] the same printout gives:
after coin 1: [1, 1, 1, 1, 1]
after coin 2: [1, 1, 2, 2, 3]
after coin 3: [1, 1, 2, 3, 4]
Step by step
- Create
waysas anint[]of sizeamount + 1. A newintarray starts with zeros: before any coin is added, no sum above 0 can be made. - Set
ways[0]to 1. The sum 0 has exactly one combination, and every other combination grows from it. - Loop over
coinswith an enhancedforloop. The coins are the outer loop, which is what makes the counts combinations. - Loop
afromcoinup toamount. A sum belowcoincan't contain it, and going up lets a smaller sum already include this coin. - Add
ways[a - coin]toways[a]. This is the key line. - Return
ways[amount]. Whenamountis 0 the loops don't run and this returnsways[0], which is 1.
The solution in Java
class Solution {
public int change(int amount, int[] coins) {
int[] ways = new int[amount + 1];
ways[0] = 1;
for (int coin : coins) {
for (int a = coin; a <= amount; a++) {
ways[a] += ways[a - coin];
}
}
return ways[amount];
}
}
The Java details worth a closer look:
- The enhanced
forloop.for (int coin : coins)visits the array's values in order. It gives you a copy of each value, which is all this code needs. - Arrays start at zero.
new int[amount + 1]fills every slot with 0, so onlyways[0]needs setting. The size isamount + 1because the indexes run from 0 toamountinclusive. - Compound assignment.
ways[a] += ways[a - coin]reads both entries and writes the sum back. Becauseacounts upward,ways[a - coin]has already been updated for this coin. intoverflow. Anintwraps silently past 2147483647. The lesson promises that the answer, and the number of combinations for every smaller amount, fits in anint, so nolongis needed here. If you reuse the idea without that promise, switch the array tolong[].
Complexity
Time: O(n · amount), where n is the number of coins. Each coin goes over at most amount + 1 sums, with constant work for each. With 300 coins and an amount of 5000, that is about 1.5 million additions.
Space: O(amount). The array ways holds amount + 1 counts, and nothing else grows with the input.
Edge cases and common mistakes
- Amount 0.
change(0, new int[]{7})returns 1: the inner loop never runs andways[0]is 1. - A coin bigger than the amount.
change(3, new int[]{2})is 0, and a coin of 10 withamount = 5is skipped, because the loop starts aboveamountand doesn't run. - A coin equal to the amount.
change(5, new int[]{5})andchange(10, new int[]{10})both return 1. - Swapping the loops. Putting the sums outside and the coins inside counts orders. For
amount = 4andcoins = [1, 2, 3]that version returns 7 instead of 4. - Looping downward. Going from
amountdown tocoinwould let each coin be used at most once, which is a different problem. - Starting
ways[0]at 0. Every count would stay 0. The empty combination is what everything else is built from.
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 = [10]gives1.amount = 5000,coins = [1, 2, 5]gives1252001.
