Problem overview
The method change receives a target amount and an array coins of different coin values. It returns how many combinations of coins add up to exactly amount, or 0 if none does. 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.
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 2s 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 can be more than a billion of them. The statement asks for O(n · amount) time and O(amount) space, where n is the number of coins. That calls for counting instead of listing.
Let ways[a] be the number of combinations that make the sum a, for every a from 0 to amount. Before any coin is used, only the sum 0 can be made (with no coins), so ways[0] is 1 and the rest are 0. The answer will be ways[amount].
Now add the coins 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 for each sum a from coin up to amount, add ways[a - coin] to ways[a]. Going upward matters: ways[a - coin] may already include this coin, which is what lets one coin value be used again and again.
Here is the array for amount = 5 and coins = [1, 2, 5], from sum 0 to sum 5, after each coin:
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 4
The last number is the answer, 4.
Why the coins are the outer loop
While a coin is being added, the counts so far use only the coins before it. So each combination is built in one fixed order: first 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 while 3 + 1 never is.
With the sums 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 = 5 and coins = [1, 2, 5] it returns 9 instead of 4.
Step by step
- Create
waysas anumber[]withamount + 1zeros, usingnew Array(amount + 1).fill(0). Indexacounts the combinations that makea. - Set
ways[0]to 1. The sum 0 has exactly one combination, and every other combination grows from it. - Loop over
coinswithfor...of. The coins are the outer loop, which is what makes the counts combinations. - Loop over the sums with
afromcoinup to and includingamount. A sum smaller than the coin can't contain it, so it is skipped. - Add
ways[a - coin]toways[a]. This is the key line: each entry reuses counts for smaller sums. - Return
ways[amount]. Foramount = 0the inner loops never run, and this returnsways[0], which is 1.
The solution in TypeScript
class Solution {
change(amount: number, coins: number[]): number {
const ways: number[] = 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];
}
}
A few TypeScript details:
new Array(n).fill(0).new Array(amount + 1)alone makes an array of empty slots, andfill(0)puts a 0 in each. The annotationnumber[]on the constant is only a compile-time check: it is erased when the code becomes JavaScript.conststill allows changes inside.waysis aconst, so the name can't be assigned to another array, but its elements can change, andways[a] += ...does that.- Sharing one object.
fillputs the same value in every slot. That is harmless for the number 0, butnew Array(3).fill([])puts the same array in all three slots, so pushing to one shows up in all of them. For a table of rows, build each row separately. - Big counts. A
numberis a double, exact for integers up to 2^53. The constraints promise that the answer and every count for a smaller amount fit in 32 bits, so the additions are exact.
Complexity
Time: O(n · amount). Each of the n coins goes over at most amount + 1 sums, with a constant amount of work for each.
Space: O(amount). ways holds amount + 1 counts, and nothing else grows with the input.
Edge cases and common mistakes
- Swapping the loops. Putting the sums outside and the coins inside counts orders. For
amount = 4andcoins = [1, 2, 3]that version returns 7, while the correct answer is 4. - Amount 0. The answer is 1, not 0. That follows from
ways[0] = 1: the empty combination. - Unreachable sums. For
amount = 3andcoins = [2],ways[3]never receives anything and stays 0. No special case is needed. - A coin larger than the amount.
change(10, [10])returns 1, while a coin larger than the amount makes the inner loop's starting value exceedamount, so it never runs and contributes nothing. - Going downward. Looping
afromamountdown tocoinwould let each coin be used at most once, which answers a different problem.
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.
