Coin Change II
Count the combinations of coins that make an amount with a 1D DP, looping over coins outside so each combination is counted once.
Problem Understanding
Coin Change II: given an amount and coin values, return the number of combinations that add up to the amount. Each coin can be used any number of times, and order does not matter.
Example: amount = 5, coins = [1, 2, 5] returns 4: 5, 2+2+1, 2+1+1+1, 1+1+1+1+1.
The Intuition: Add One Coin Type at a Time
Let dp[a] be the number of ways to make a using the coin types seen so far. Start with no coins: only dp[0] = 1.
Now allow one more coin type, c. A combination for amount a either uses no c (already counted in dp[a]) or uses at least one, leaving a − c to make with the same coins, c included. So:
dp[a] += dp[a − c]forafromcup toamount.
Because one coin type is finished before the next starts, every combination is built in the same coin order, and nothing is counted twice. Swap the two loops and you count ordered sequences instead: that is Combination Sum IV. For the fewest coins rather than the number of ways, see Coin Change.
Interactive Walkthrough
The coins are on top, with the one being added marked. Below, each coin sweeps the dp row left to right: a is marked, and the cell it adds, dp[a − coin], is shaded. Every new coin makes the counts grow again.
Dry Run Table
Input: amount = 5, coins = [1, 2, 5]
| After coin | dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | dp[5] |
|---|---|---|---|---|---|---|
| (none) | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 | 2 | 3 | 3 |
| 5 | 1 | 1 | 2 | 2 | 3 | 4 |
The Solution Template
Unbounded knapsack counting combinations: coins outside, amounts inside, ascending.
Coin Change II Code
1var change = function(amount, coins) {2 const dp = new Array(amount + 1).fill(0);3 dp[0] = 1;4 for (const coin of coins) {5 for (let a = coin; a <= amount; a++) {6 dp[a] += dp[a - coin];7 }8 }9 return dp[amount];10};
Edge Cases & Common Mistakes
- amount = 0: the answer is
1, the empty combination. - Swapping the loops: amounts outside counts orders, giving 7 instead of 4 for amount 4 with coins [1, 2, 3].
- Overflow in C and C++: intermediate counts for amounts the answer never uses can exceed 32 bits; an unsigned 64-bit row avoids the overflow error, and the final answer fits in an int.
- Unreachable amount:
dp[amount]simply stays0, as with amount 3 and coins [2].
Summary
dp[a] counts the combinations that make a. Start from dp[0] = 1, then add coins one at a time with dp[a] += dp[a − coin] for a ascending from the coin. Coins on the outside means each combination is counted once. O(amount · coins) time, O(amount) space.
More practice: DSA interview questions with answers · patterns cheat sheet