Coin Change

Coin Change — Counting Combinations (Unbounded Knapsack)

The number of ways to make amount T from unlimited-supply coins is built up by deciding, one coin denomination at a time, how many copies of that coin to use — each decision either reuses a smaller amount's already-computed answer (dp[j-coin], allowing the same coin again) or leaves the count untouched (skip the coin), so the table fills as a running accumulation rather than a fresh choice per amount.

Recognize the pattern

• "Infinite supply" / "each item can be reused any number of times" → unbounded knapsack, not 0/1.
• Question asks how many distinct combinations (order doesn't matter: {1,2,2} ≡ {2,1,2}) → this is the subset-sum counting variant, distinct from "minimum coins" (optimization) or "number of ordered sequences" (permutation-counting, e.g. Climbing Stairs with variable steps).
• State needed is exactly two numbers: which coins considered so far, and remaining amount — screams 2D table collapsible to 1D.

Brute force → optimal

Brute force: recursion — for each coin, branch into "use it (amount shrinks, coin stays available)" vs "move to next coin". Recurrence: ways(i, amt) = ways(i, amt-coins[i]) + ways(i+1, amt), base cases amt==0 → 1, amt<0 or i==n → 0. A single low-value coin does not cause blow-up: with coins={1}, amount=T, the "skip" branch hits i==n and returns 0 immediately at every level, so ways(0,T) makes only ~2T+1 calls total — linear, not exponential. Real blow-up needs many coins with count comparable to T, because then both the "use" and "skip" branches stay alive for many levels simultaneously. Concretely: coins = T copies of denomination 1 (n=T coin slots), amount=T. The recurrence ways(i,amt)=ways(i,amt-1)+ways(i+1,amt) then matches the recurrence for counting monotone lattice paths from (0,T) to the boundary, and the call count grows like C(2T,T) ≈ 4^T/√T — exponential in T, but shaped by combinatorial path-counting, not a clean 2^T.

Optimal: memoize (i, amt) → O(n·T) distinct states, O(1) work each, giving O(n·T) time. Because row i only reads row i (same coin, smaller amount) and row i-1, the 2D table collapses to a single 1D array of size T+1, updated in place per coin.

Complexity, derived

Let n = number of coins, T = target amount. The DP conceptually fills an (n+1)×(T+1) grid; the 1D-collapsed version is one array of size T+1 refreshed n times. Total cell visits = n × (T+1), each visit doing one addition and one bound check — O(1) work → time = Θ(n·T). Space: only the current 1D array is kept → Θ(T), versus Θ(n·T) for the full 2D table (needed only if you must reconstruct which coins were used, not just count). This is the payoff of memoization: the unmemoized recursion above can reach Θ(C(2T,T)) calls when n is comparable to T, while memoizing collapses it to the Θ(n·T) states that actually exist — a real, demonstrated blow-up, not an asserted one.

Worked example

coins = {1,2,3}, amount = 5. dp[j] = ways to make j using coins processed so far. Init dp = [1,0,0,0,0,0] (dp[0]=1: one way to make 0, use no coins).

Final dp[5] = 5 — matches the five combinations {1,1,1,1,1}, {1,1,1,2}, {1,2,2}, {1,1,3}, {2,3}.

Java — combinations (order doesn't matter)

int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int coin : coins) {              // outer: coin
        for (int j = coin; j <= amount; j++) { // inner: amount, ascending
            dp[j] += dp[j - coin];
        }
    }
    return dp[amount];
}

Pitfalls

• Loop order flip changes the question. Swapping to amount-outer, coin-inner counts ordered sequences (permutations), not combinations — e.g. for coins {1,2}, amount 3 that variant counts {1,1,1},{1,2},{2,1} as 3 distinct ways instead of 2.
• In-place ascending update relies on unbounded reuse. Updating dp[j] from a value already updated within the same coin's pass (ascending j) is what allows reusing the same coin multiple times; for 0/1 knapsack (each coin used at most once) you must iterate j descending instead.
• dp[0] = 1, not 0 — forgetting this base case zeroes out the whole table.
• Integer overflow: use long if amount and coin count are large enough that the way-count can exceed int range.

When to use / when NOT — trade-offs

Use this 1D unbounded-DP pattern whenever coins are reusable and you need a count or optimum over amounts up to T with T not too large (state space n·T must be tractable, e.g. T ≤ 10^4 as here).

• vs. 0/1 Knapsack (each coin usable once): same table shape, but iterate the amount dimension descending to prevent reusing an item within its own pass. Use 0/1 when supply is limited per item.
• vs. BFS on amounts (for "minimum coins" specifically): BFS also gives O(n·T) but naturally computes shortest path / fewest coins and short-circuits early; DP is more natural when you need *all* subproblem values (as counting requires) rather than just the target.
• vs. brute-force recursion with memoization: identical asymptotic cost once memoized, but the iterative table avoids recursion-stack overhead and is easier to space-optimize to O(T).
• Don't reach for this when amount T is astronomically large relative to coin values (e.g. T ~ 10^9) — O(n·T) DP is infeasible; that regime needs number-theoretic / matrix-exponentiation techniques instead.

Takeaways

• Counting combinations with unlimited supply = process denominations one at a time, accumulate into a 1D array indexed by amount.
• Loop order (coin-outer vs amount-outer) is the entire difference between counting combinations and permutations.
• Ascending vs descending inner-loop direction is the entire difference between unbounded (0/1-knapsack-style) and bounded (0/1 knapsack) reuse.
• dp[0] = 1 is the seed that makes every other count possible.
• Unmemoized recursion blows up only when many coins are comparable in count to T (both branches stay live), not from a single small denomination — a single coin=1 recursion is linear, not exponential.

Recall: Why does processing coins in the outer loop (rather than amounts in the outer loop) guarantee each combination is counted exactly once, not once per ordering?

Compiled from LeetCode 518 (Coin Change II) problem framing and standard unbounded-knapsack DP derivations; worked example, the brute-force blow-up example (re-derived to actually exhibit exponential growth), complexity analysis, and diagrams are original to this page.