The problem. Given coin values coins (unlimited supply of each) and an amount, return the number of combinations of coins that make up amount. Order doesn't matter: 1 + 2 and 2 + 1 are the same combination.
![coins are 1, 2 and 5, amount 5. The row ways[0..5] is updated once per coin. It starts as 1, 0, 0, 0, 0, 0. After coin 1 every amount has 1 way. After coin 2 it is 1, 1, 2, 2, 3, 3: for example ways[4] = 1 (the old value, without any 2) + ways[2] = 2, giving 3. After coin 5 it is 1, 1, 2, 2, 3, 4. The 4 combinations are 5; 2 + 2 + 1; 2 + 1 + 1 + 1; and 1 + 1 + 1 + 1 + 1.](/drawings/75bee465-0ff6-4393-9b0a-ce68034c2528.svg)
amount = 5, coins = [1, 2, 5] -> 4
amount = 3, coins = [2] -> 0
amount = 10, coins = [10] -> 1
amount = 0, coins = [7] -> 1 (take no coins)Counting the last coin like Coin Change would count 1 + 2 and 2 + 1 separately. To count each combination once, fix an order on the coin types: first decide how many 1s, then how many 2s, then how many 5s. For coin i there are two choices — use one more coin `i` (and stay on coin i, since it can repeat) or move on to coin i + 1 for good. Every combination is built in exactly one way, so nothing is double-counted.
function change(amount, coins) { const memo = new Map(); // "i,left" -> combinations const ways = (i, left) => { // combinations of coins[i..] that make left if (left === 0) return 1; if (i === coins.length) return 0; const key = i + "," + left; if (memo.has(key)) return memo.get(key); let count = ways(i + 1, left); // no more of coin i if (coins[i] <= left) count += ways(i, left - coins[i]); // one more coin i: stay on i memo.set(key, count); return count; }; return ways(0, amount);}Time O(k · amount), space O(k · amount) for k coin types.
function change(amount, coins) { const k = coins.length; // ways[i][a]: combinations that make a using only the first i coin types const ways = Array.from({ length: k + 1 }, () => new Array(amount + 1).fill(0)); for (let i = 0; i <= k; i++) ways[i][0] = 1; // amount 0: take nothing for (let i = 1; i <= k; i++) { const c = coins[i - 1]; for (let a = 1; a <= amount; a++) { ways[i][a] = ways[i - 1][a]; // no coin c at all if (c <= a) ways[i][a] += ways[i][a - c]; // at least one c: same row, so c can repeat } } return ways[k][amount];}Time O(k · amount), space O(k · amount). Look at where each cell reads from: the row above (skip coin c) and its own row, c to the left (use c again). Reading its own row is what makes the knapsack unbounded.
Each coin pass adds the combinations that use that coin.
function change(amount, coins) { const ways = new Array(amount + 1).fill(0); // ways[a]: combinations that make a ways[0] = 1; // take nothing for (const c of coins) { // coins outside: each combination counted once for (let a = c; a <= amount; a++) ways[a] += ways[a - c]; // forwards: c can repeat } return ways[amount];}Time O(k · amount), space O(amount). The row-per-coin table collapses into one row because each cell reads the row above at the same index (which is still in place) and its own row to the left (already updated). The loop runs forwards — the opposite of Partition Equal Subset Sum — precisely so ways[a - c] already includes coin c.
Why C++ uses `unsigned`. LeetCode promises the answer fits in a 32-bit int, but counts for smaller amounts along the way can be far bigger. Signed overflow is undefined behaviour in C++; unsigned arithmetic wraps around, and because only additions are involved, the final answer still comes out right. Java's int wraps the same way by definition.
Swap the two loops and the meaning changes. With amounts outside, every amount tries every coin as its last one, so 1 + 2 and 2 + 1 are counted separately — that counts orderings:
for a in 1..amount: // amounts outside, coins inside
for c in coins:
if c <= a: ways[a] += ways[a - c]
amount 3, coins [1, 2]: coins outside -> 2 (1+1+1, 1+2)
amounts outside -> 3 (1+1+1, 1+2, 2+1)That second version is exactly Combination Sum IV. Remember it as: coins outside = combinations, amounts outside = permutations.
[2] and 3: 0.[10] and 10: 1.