Coin Change II: Counting Combinations Without Double-Counting
Count the ways to make an amount from coin denominations. Coin Change II explained with the combinations DP, a worked trace, JavaScript code, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Coin Change II looks like its famous cousin — same coins, same target amount — but it asks a fundamentally different question. The original Coin Change wants the fewest coins. This one wants the number of ways. And that one word, "ways," hides the single trap that catches almost everyone on the first attempt: counting 1 + 2 and 2 + 1 as two different answers when they are the same combination.
Get past that trap and you've learned the unbounded knapsack pattern — the template for "how many ways can I fill a capacity from an unlimited supply of items." It powers combination-counting problems across the entire DP catalog.
The problem
You're given an array coins of distinct denominations and an integer amount. You have an unlimited supply of each coin. Return the number of distinct combinations that sum to exactly amount. Order does not matter, so {1, 2} and {2, 1} count once, not twice.
Input: amount = 5, coins = [1, 2, 5]
Output: 4
The four combinations:
5 = 5
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1Two properties shape everything below:
- Unlimited supply — a single coin can be reused, so this is unbounded, not the 0/1 knapsack where each item is used at most once.
- Combinations, not permutations —
{2, 1, 1, 1}and{1, 2, 1, 1}are the same answer. Enforcing a single canonical order is the whole game.
The brute force baseline
The naive recursion asks: "how many ways to make remS if, at every step, I'm free to pick any coin?"
function changeBrute(amount, coins) {
function ways(remS) {
if (remS === 0) return 1;
if (remS < 0) return 0;
let total = 0;
for (const coin of coins) { // any coin, every time
total += ways(remS - coin);
}
return total;
}
return ways(amount);
}This is wrong before it's even slow. With amount = 3, coins = [1, 2] it returns 3, not 2 — it counts 1 + 2 and 2 + 1 as separate paths. On top of the correctness bug, it re-solves the same remS exponentially many times, so it's O(2^amount) in the worst case. We need to fix both the over-counting and the recomputation.
The key insight: fix the order with a start index
The over-counting comes from letting every recursive call reach for any coin. The fix is to impose an order: once you've moved past a denomination, you can't go back to it.
Carry a second parameter, start — the index of the first coin you're still allowed to use. Each call only loops over coins from start onward:
fn(remS, start) = sum of fn(remS - coins[i], i) for i in [start .. n-1]Two subtle but critical details:
- The loop starts at
start, never0, so a combination is always built in non-decreasing index order.{1, 2}gets counted;{2, 1}can never form because after picking coin index 1 you can't loop back to index 0. - The recursive call passes
i, noti + 1— that's what keeps the coin reusable. Staying on the same index lets you pick1 + 1 + 1; advancing toi + 1would forbid reuse and turn this into 0/1 knapsack.
Then memoize on (remS, start) so each state is computed once. That kills the exponential blowup.
The optimal solution
This is the exact top-down memoized recursion the Coin Change II visualizer steps through:
var change = function(amount, coins) {
let n = coins.length;
let dp = Array.from({ length: amount + 1 }, () => Array(n).fill(-1));
let fn = (remS, start) => {
if (remS === 0) return 1; // exact hit: one full combination
if (remS < 0) return 0; // overshot: dead path
if (dp[remS][start] != -1) return dp[remS][start]; // memo hit
let combinations = 0;
for (let i = start; i < n; i++) {
combinations += fn(remS - coins[i], i); // reuse coin i, never go back
}
return dp[remS][start] = combinations;
};
return fn(amount, 0);
};The memo table dp[remS][start] caches "how many combinations make remS using coins from index start onward." Initialized to -1 (meaning uncomputed, distinct from a real answer of 0). remS === 0 returns 1 because reaching zero means the coins picked so far form one complete combination. remS < 0 returns 0 because we overshot the target.
Walkthrough
Trace amount = 3, coins = [1, 2]. The answer is 2: {1, 1, 1} and {1, 2}. Each row is one recursive call; the depth column shows how deep the call stack is.
| Depth | Call | What happens | Returns |
|---|---|---|---|
| 0 | fn(3, 0) | i=0 (coin 1) → recurse | pending |
| 1 | fn(2, 0) | i=0 (coin 1) → recurse | pending |
| 2 | fn(1, 0) | i=0 (coin 1) → recurse | pending |
| 3 | fn(0, 0) | base: remS === 0 | 1 |
| 2 | fn(1, 0) | i=1 (coin 2) → fn(-1, 1) | pending |
| 3 | fn(-1, 1) | base: remS < 0 | 0 |
| 2 | fn(1, 0) | 1 + 0, set dp[1][0] = 1 | 1 |
| 1 | fn(2, 0) | i=1 (coin 2) → fn(0, 1) | pending |
| 2 | fn(0, 1) | base: remS === 0 | 1 |
| 1 | fn(2, 0) | 1 + 1, set dp[2][0] = 2 | 2 |
| 0 | fn(3, 0) | i=1 (coin 2) → fn(1, 1) | pending |
| 1 | fn(1, 1) | fn(-1, 1) = 0, set dp[1][1] = 0 | 0 |
| 0 | fn(3, 0) | 2 + 0, set dp[3][0] = 2 | 2 |
Notice fn(1, 1) returns 0, not 1. From start = 1 the only allowed coin is 2, and you can't make 1 with a 2. That's the ordering constraint doing its job — the {1} that would complete a {2, 1} permutation is off-limits because index 0 is behind us. The final dp[3][0] = 2 is the answer.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(amount × n²) | O(amount × n) distinct (remS, start) states, each running a loop of up to n coins |
| Space | O(amount × n) | the memo table, plus recursion depth up to O(amount) on the call stack |
Here n = coins.length. The memoization is what makes it polynomial — without it the recursion is exponential. A bottom-up 1D DP (iterate coins on the outer loop, amounts on the inner) computes the same answer in a tighter O(amount × n) time and O(amount) space, but the top-down version above maps one-to-one onto the recurrence, which makes the combinations-vs-permutations logic easier to see.
Common mistakes
- Looping every coin on every call. That's the brute-force bug — it counts permutations. The
startindex is the fix; the inner loop must begin atstart, not0. - Passing
i + 1instead ofi. Advancing the index forbids coin reuse and silently solves the 0/1 knapsack ("each coin at most once") instead. For unbounded supply, stay oni. - Initializing the memo to
0. A legitimately computed answer can be0(seefn(1, 1)above). Use a sentinel like-1so "uncomputed" and "zero ways" stay distinguishable — otherwise you never trust the cache and recompute forever. - Swapping the loop order in the bottom-up version. If you put amount on the outer loop and coins on the inner, you count permutations again. Coins must be the outer loop so each denomination is fully absorbed before the next.
- Integer overflow in other languages. The count can exceed 32-bit range for large inputs; in Java/C++ you may need
long. JavaScript numbers handle it up to 2^53.
Where this pattern shows up next
Coin Change II is combination-counting DP. Once the "add up the ways from smaller subproblems" reflex clicks, these neighbors read the same way:
- Fibonacci Number — the simplest "sum of two subproblems" recurrence, and the cleanest place to first meet memoization.
- Climbing Stairs — literally Coin Change with steps
{1, 2}where order does matter, so it counts permutations instead. - Min Cost Climbing Stairs — the same 1D DP walk, but minimizing a cost rather than counting ways.
- House Robber — a take-it-or-skip-it choice per element, the decision-DP sibling of this counting problem.
You can also step through Coin Change II interactively to watch the memo table dp[remS][start] fill in and the combination count roll up, one recursive call at a time.
FAQ
Why doesn't Coin Change II count 1 + 2 and 2 + 1 separately?
Because the recursion carries a start index and each call only uses coins from that index onward. Once a combination includes a coin at index 1, later picks can't reach back to index 0, so coins are always chosen in non-decreasing index order. {1, 2} forms as a single canonical path and {2, 1} never forms at all. Remove the start parameter and you'd count permutations, which is a different problem (that's what Climbing Stairs does).
What is the difference between Coin Change and Coin Change II?
The original Coin Change asks for the minimum number of coins to make the amount, returning -1 if impossible — it's a minimization problem. Coin Change II asks for the number of distinct combinations that sum to the amount — it's a counting problem. Different recurrences: minimization takes a min over choices, counting takes a sum. They share the coins-and-amount framing but almost nothing else in the DP.
Why is the memo table initialized to -1 instead of 0?
Because 0 is a valid answer — some (remS, start) states genuinely have zero combinations, like making 1 when the only allowed coin is 2. If you used 0 as the "not yet computed" marker, you couldn't tell an uncomputed cell from a legitimately-zero one, so the cache would never register those results and you'd recompute them endlessly. The -1 sentinel keeps "uncomputed" and "zero ways" distinct.
Is Coin Change II an unbounded knapsack problem?
Yes. Each coin can be used an unlimited number of times, which is the defining trait of unbounded knapsack (versus 0/1 knapsack, where each item is used at most once). The reuse is encoded by the recursive call passing i rather than i + 1, letting the same denomination be picked again. Counting combinations that hit an exact capacity is the canonical unbounded-knapsack counting variant.
What is the time complexity of Coin Change II?
The memoized top-down solution runs in O(amount × n²) time, where n is the number of coin denominations: there are O(amount × n) distinct memo states, and each runs a loop over up to n coins. Space is O(amount × n) for the memo table plus O(amount) recursion depth. A bottom-up 1D DP tightens this to O(amount × n) time and O(amount) space while computing the identical answer.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.