Problem overview
The method change(amount, coins) receives a target amount 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
1 + 1 + 1 + 1 + 1
With amount = 3 and coins = [2] the answer is 0, because coins of 2 only make even sums. When amount is 0 the answer is 1: the combination of no coins at all.
Approach: count the ways for every smaller sum
Listing every combination is hopeless: with a few dozen coins and an amount of 5000 there are over a billion of them. The lesson counts instead. Let ways[a] be the number of combinations that make the sum a, for every a from 0 to amount. The answer is ways[amount].
The table starts with ways[0] = 1 (no coins) and zeros everywhere else, because before any coin is available nothing above 0 can be made. Then the coins are added one at a time. For a coin, every combination that makes a - coin, plus one more of this coin, is a combination that makes a. So ways[a] grows by ways[a - coin].
Why the order of the loops matters
The coins form the outer loop and the sums form the inner loop. While one coin is being added, the counts in ways only use the coins before it. Every combination is therefore built in one fixed order: first all its coins of the first value, then all of the second value, and so on. 1 + 3 gets built, but 3 + 1 never does, so each combination is counted once.
Swapping the loops (sums outside, coins inside) lets any coin be the last one added to any sum, and then 1 + 3 and 3 + 1 are both counted. That counts ordered sequences, not combinations. For amount = 4 and coins = [1, 2, 3] the correct answer is 4, and the swapped loops return 7.
The inner loop goes upward from coin. That way ways[a - coin] already includes the current coin when ways[a] reads it, which allows the same coin value to be used again and again.
Here is the array after each coin for amount = 5 and coins = [1, 2, 5], with the entries for the sums 0 to 5:
start: [1,0,0,0,0,0]
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]
The last entry is 4, the answer.
Step by step
- Create
wayswithconst:amount + 1zeros, built withnew Array(amount + 1).fill(0). It needs one slot for every sum from 0 toamount. - Set
ways[0]to 1. Every combination grows from the combination of no coins. - Loop over the coins with
for...ofand aconstnamedcoin. This is the outer loop, which keeps the counts about combinations. - Loop over the sums with
let a = coin, going up whilea <= amount. A sum smaller than the coin can't contain it, so the loop starts at the coin's value. - Add
ways[a - coin]toways[a]with+=. This is the key line: each entry reuses counts for smaller sums. - Return
ways[amount]after the outer loop. Whenamountis 0 the inner loops never run, and this returnsways[0], which is 1.
The solution in JavaScript
class Solution {
change(amount, coins) {
const ways = new Array(amount + 1).fill(0);
ways[0] = 1;
for (const coin of coins) {
for (let a = coin; a <= amount; a++) {
ways[a] += ways[a - coin];
}
}
return ways[amount];
}
}
The JavaScript details worth a closer look:
new Array(n).fill(0)creates an array ofnempty slots and then fills every one with0. Withoutfill, the slots would be empty andways[a] += ...would add toundefined, which givesNaN.constdoes not freeze the array. It only stops the namewaysfrom being assigned a different array. The entries can still change, which is why+=onways[a]works.for...ofversusfor...in.for (const coin of coins)gives the values.for...inwould give the indexes as strings.- Numbers are doubles. They represent integers exactly up to
Number.MAX_SAFE_INTEGER, 9007199254740991. The statement promises that every count fits in a 32-bit integer, so sums never get near that limit, and no overflow can occur.
Complexity
Time: O(n · amount), where n is the number of coins. Each coin goes over at most amount + 1 sums, with a constant amount of work for each.
Space: O(amount). The only extra memory is ways, with amount + 1 counts. It is a single row, because the counts for the coins so far are updated in place.
Edge cases and common mistakes
- Amount 0.
change(0, [7])returns 1: the one combination of no coins. - Coin larger than the amount.
change(3, [5])returns 0, andchange(10, [10])returns 1. For a coin bigger thanamountthe inner loop starts past the end and does nothing. - Swapped loops. Sums outside and coins inside counts orders: 7 instead of 4 for
amount = 4andcoins = [1, 2, 3]. - Starting
ways[0]at 0. Every entry would stay 0, since all counts grow from that first 1. - Going downward in the inner loop. A loop from
amountdown tocoinlets each coin be used at most once. That would solve a different problem, in which every coin can be taken only once. - Off-by-one in the table size. Creating
amountentries instead ofamount + 1leaves no slot forways[amount], which would beundefined.
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.
