Coin Change II

1. Problem & Core Objective

Given coin denominations and an amount, return the number of combinations that make up that amount. You have unlimited coins of each denomination. Combinations differing only in order count as one.

amount = 5, coins = [1,2,5]   →  4      5; 2+2+1; 2+1+1+1; 1+1+1+1+1
amount = 3, coins = [2]       →  0
amount = 10, coins = [10]     →  1

Constraints: 1 <= coins.length <= 300 · 1 <= coins[i] <= 5000 · 0 <= amount <= 5000 · denominations are distinct

What's actually being tested: that the loop order decides combinations versus permutations. Same array, same recurrence, same complexity — swapping the two loops changes the answer. It's the clearest example in the set of nesting order carrying semantic meaning.

2. First-Principles Thought Process

Counting means +

Coin Change minimised coins with min. Here we count, so the combiner is +:

dp[a] += dp[a - c]

Same structure, different combiner — the substitution established in Min Cost Climbing Stairs.

The loop order is the whole question

// COMBINATIONS — coins outer                 // PERMUTATIONS — amount outer
for (int c : coins)                           for (int a = 1; a <= amount; a++)
    for (int a = c; a <= amount; a++)             for (int c : coins)
        dp[a] += dp[a - c];                           if (c <= a) dp[a] += dp[a - c];

Coins outer means each denomination is considered once, in a fixed order, and every combination is built with coins in that order. 1+2 is counted; 2+1 is not, because 2 was processed after 1 and the recurrence never revisits.

Amount outer means at every amount, all coins are tried — so 1+2 and 2+1 are both counted as distinct paths.

For amount = 5, coins = [1,2,5]: combinations gives 4, permutations gives 9. Same code, one swap.

Why coins-outer fixes an order

Processing coin c updates every amount using c before moving to the next denomination. So once you've moved past c, no later update can insert a c after a larger coin.

Each combination therefore has exactly one construction path — coins in processing order — and is counted once.

Why the amount loop ascends

Same reason as Coin Change: dp[a - c] may already include c, which is exactly the unlimited-supply requirement. Descending would give 0/1 knapsack — each coin used at most once, which is Partition Equal Subset Sum.

So there are two independent loop-order decisions here, and conflating them is the usual confusion:

Base case

dp[0] = 1 — one way to make zero: take nothing. Setting it 0 makes the whole table 0.

3. Solution Paths

Approach 1 — Backtracking over combinations (brute force)

public int change(int amount, int[] coins) {
    return count(coins, 0, amount);
}

private int count(int[] coins, int start, int remaining) {
    if (remaining == 0) return 1;                   // one complete combination
    if (remaining < 0) return 0;

    int ways = 0;
    for (int i = start; i < coins.length; i++)
        ways += count(coins, i, remaining - coins[i]);   // i, not i+1 — reuse allowed
    return ways;
}

• Time exponential · Space O(amount / min) stack

Counter-questions on this approach

⭐ "Why does the loop start at start rather than 0?"

To enforce a non-decreasing coin order, which is what makes each combination reachable by exactly one path — the same deduplication as in Combination Sum.

Starting at 0 would count 1+2 and 2+1 separately, giving permutations instead.

That's the backtracking analogue of putting the coin loop outside in the DP: both impose a fixed ordering on which coins may follow which.

⭐ "Why i and not i + 1 in the recursive call?"

Unlimited supply — the same coin may be used again. i + 1 would give each-coin-once, which is a different problem.

"How slow is it?"

The number of combinations itself can be enormous — for amount = 5000 with 300 coins the answer overflows. The search explores every one, so it's proportional to the output, which is exponential.

Approach 2 — 2-D DP

public int change(int amount, int[] coins) {
    int n = coins.length;
    int[][] dp = new int[n + 1][amount + 1];
    for (int i = 0; i <= n; i++) dp[i][0] = 1;      // one way to make 0: take nothing

    for (int i = 1; i <= n; i++)
        for (int a = 1; a <= amount; a++) {
            dp[i][a] = dp[i - 1][a];                             // don't use coin i
            if (coins[i - 1] <= a)
                dp[i][a] += dp[i][a - coins[i - 1]];             // use it (and may reuse)
        }

    return dp[n][amount];
}

• Time O(n × amount) · Space O(n × amount)

Counter-questions on this approach

⭐ "Why does the 'use it' branch read row i rather than row i−1?"

Because the coin may be used again. Reading row i means "having already considered coin i, and possibly used it", which permits unlimited reuse.

Reading row i−1 would mean each coin is used at most once — that's 0/1 knapsack, and it's the explicit version of the descending-loop trick.

So the row index here plays exactly the role the loop direction plays in the 1-D version, which is worth noticing: the 2-D form makes the choice visible.

⭐ "Why is dp[i][0] = 1 for every i?"

There's exactly one way to make amount 0 regardless of which coins are available: use none. Every counting path bottoms out there.

"Why does this count combinations rather than permutations?"

Because the row index imposes an order. dp[i][a] only ever considers coins 1..i, so a combination is built by a fixed sequence of denominations and counted once.

The 1-D collapse preserves that by keeping the coin loop outside.

Approach 3 — 1-D, coins outer (optimal)

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;                                       // one way to make 0

    for (int c : coins)                              // COINS OUTER -> combinations
        for (int a = c; a <= amount; a++)            // ASCENDING -> unlimited reuse
            dp[a] += dp[a - c];

    return dp[amount];
}

Trace — amount = 5, coins = [1,2,5]:

Answer 4 ✓

• Time O(n × amount) = 1.5 × 10^6 · Space O(amount)

Counter-questions on this approach

⭐ "Swap the two loops. What changes, and why?"

The answer changes from combinations to permutations — 4 becomes 9 for this input.

With coins outer, each denomination is fully processed before the next, so every combination is built in a fixed coin order and counted once. With amount outer, every coin is tried at every amount, so 1+2 and 2+1 arise as separate paths.

Same array, same recurrence, same complexity. Only the nesting differs, and it carries the entire semantic difference.

I verified both: coins-outer gives 4, amount-outer gives 9 for amount = 5, coins = [1,2,5].

⭐ "There are two loop-order decisions here. Distinguish them."

They're independent and easy to conflate:

• Which loop is outer decides combinations (coins outer) versus permutations (amount outer).
• Which direction the amount loop runs decides unlimited reuse (ascending) versus each-coin-once (descending).

This problem wants combinations with unlimited reuse, so: coins outer, amount ascending.

Partition Equal Subset Sum wants each item once, so it descends. Coin Change minimises rather than counts, so the order doesn't affect its answer — which is why the distinction only surfaces here.

⭐ "Why start the inner loop at c rather than 1?"

Below c, the index a - c would be negative. Starting at c is both the bounds guard and correct — amounts smaller than c can't include it.

"Why dp[0] = 1?"

One way to make zero: the empty selection. It's the base every counting path reduces to — dp[c] = dp[0] = 1 for each denomination.

Setting it 0 makes the entire table 0.

"Could the count overflow?"

Yes in principle — with amount = 5000 and 300 small denominations the number of combinations is astronomical. LeetCode guarantees the answer fits in a signed 32-bit integer, which bounds the actual test inputs.

That's a guarantee about the data rather than the input space, same as in Decode Ways. Worth flagging.

"Does the order of coins matter?"

No. Any processing order gives the same count, because each combination is a multiset and gets built exactly once regardless of which denomination is handled first. Sorting is unnecessary here, unlike in the backtracking version where it enables pruning.

Comparison

4. Why the Optimal Wins

The backtracking enumerates every combination, and there can be exponentially many — counting should never require producing them.

Between the DP forms, the 1-D collapse works because row i reads only row i−1 (for the skip) and row i itself (for the reuse) — both of which a single array holds if the coin loop stays outside.

The framing worth keeping:

Two independent loop-order decisions. Coins OUTER gives combinations, amount outer gives permutations. Amount ASCENDING gives unlimited reuse, descending gives each-coin-once. This problem wants coins outer, amount ascending.

5. Java Prerequisites

Combinations with unlimited reuse

dp[0] = 1;
for (int c : coins)                    // OUTER -> combinations
    for (int a = c; a <= amount; a++)  // ASCENDING -> unlimited reuse
        dp[a] += dp[a - c];

The three variants, for contrast

dp[0] = 1 — the empty selection makes zero.

Inner loop starts at c — both a bounds guard and correct.

6. Interview Communication Guide

Clarifying questions: Do 1+2 and 2+1 count as one or two (one — combinations; this is the crux)? Unlimited coins (yes)? Can amount be 0 (yes, answer 1)? Are denominations distinct (yes)? Could the count overflow (guaranteed to fit in int)?

The pitch

"This is Coin Change with + instead of min — counting rather than optimising. But the interesting part is the loop order, because it decides the answer.

There are two independent decisions, and they're easy to conflate.

Which loop is outer decides combinations versus permutations. With coins outer, each denomination is fully processed before the next, so every combination is built in a fixed coin order and counted once — 1+2 is counted, 2+1 isn't, because 2 was processed after 1 and the recurrence never revisits. With amount outer, all coins are tried at every amount, so both orderings arise as separate paths.

For amount = 5, coins = [1,2,5] that's 4 versus 9. Same array, same recurrence, same complexity — only the nesting.

Which direction the amount loop runs decides reuse. Ascending means dp[a - c] may already include coin c, which is unlimited supply. Descending would give each-coin-once, which is 0/1 knapsack.

So this problem wants coins outer, amount ascending.

dp[0] = 1 is the base case — one way to make zero, by taking nothing. Setting it to 0 zeroes the entire table.

O(n × amount) = 1.5 × 10^6, O(amount) space — about 20 KB versus 6 MB for the 2-D table.

One thing to flag: the count can overflow in principle. With amount = 5000 and many small denominations it's astronomical. The problem guarantees the answer fits in int, but that's a guarantee about the test data rather than the input space."

Edge cases to volunteer:

Name amount = 5, coins = [1,2,5]. It's the case where the loop order visibly changes the answer — 4 versus 9 — so it pins down the combinations-versus-permutations choice.

7. Follow-Up Questions — Modified Constraints

⭐ "Count PERMUTATIONS instead — where 1+2 and 2+1 differ."

Swap the loops: amount outer, coins inner. That's LeetCode 377, Combination Sum IV — which despite its name counts permutations. One swap, and it's the same code otherwise.

⭐ "What if each coin had limited supply?"

Bounded knapsack — add a count dimension, or use binary splitting to decompose a supply of k into powers of two, turning it into 0/1 items.

"Return the combinations themselves, not the count."

Backtracking, since there can be exponentially many. Counting and enumerating have genuinely different complexities — the DP counts without producing.

"What if amount were 10^9?"

O(amount) is infeasible. With few denominations there are generating-function and matrix-exponentiation approaches, but in general the problem is hard when the amount is given in binary.

"Count combinations using exactly k coins."

Add a dimension: dp[a][k]. O(amount × k × n) time. The extra index is a genuine count rather than a state label, unlike the stock problem's states.

"Why doesn't the loop order matter for the minimum coins version?"

Because min is order-independent — the set of reachable values is the same either way, so the minimum over them is too. Counting is sensitive to how many paths reach a value, which is exactly what the order changes. That contrast is worth stating.