Coin Change II LeetCode 518 — DP Guide

LeetCode 518 Coin Change II gives you an array of distinct coin denominations and a target amount. Your task is to return the number of combinations of coins that make up exactly that amount. You have an unlimited supply of each coin denomination. The order of coins does not matter: [1, 2] and [2, 1] are considered the same combination and should be counted only once.

This is a counting problem, not an optimisation problem. Unlike Coin Change I (LeetCode 322) which asks for the minimum number of coins, Coin Change II asks how many distinct combinations exist. The answer can be 0 if no combination reaches the target, or a large integer for generous coin sets — the problem guarantees the answer fits in a 32-bit signed integer.

The problem is a classic instance of the unbounded knapsack counting variant: items (coins) have unlimited quantity, each item has a weight (denomination), and you want to count the number of ways to fill a knapsack of exact capacity (amount). Recognising this framing immediately suggests a 1D DP solution and, critically, the loop order that produces combinations rather than permutations.

Coin Change I (LeetCode 322) is an optimisation problem: find the minimum number of coins needed to make up the amount, or return -1 if it is impossible. The DP recurrence is dp[i] = min(dp[i], dp[i - coin] + 1) for each coin. The answer is dp[amount] if it is not infinity, otherwise -1. This is the "0/1 knapsack minimum cost" pattern applied with unlimited coin use.

Coin Change II (LeetCode 518) is a counting problem: count the number of distinct combinations. The DP recurrence is dp[i] += dp[i - coin] for each coin. The answer is dp[amount]. While the recurrence looks simpler, the loop order is critical and counterintuitive — getting it wrong silently produces an incorrect answer that overcounts permutations as if they were distinct combinations.

The two problems share the same coin array and the same DP array structure, but the semantics are entirely different. Coin Change I minimises; Coin Change II counts. Coin Change I uses min(); Coin Change II uses +=. And Coin Change II requires the coins in the outer loop — a constraint Coin Change I does not have because min() is commutative and order-insensitive for optimisation.

Define dp as a 1D array of length (amount + 1) initialised to 0. dp[i] represents the number of combinations of coins (from the coins seen so far in the outer loop) that sum to exactly i. The base case dp[0] = 1 encodes that there is exactly one way to make amount 0: use no coins at all. This is the empty combination, and it is the foundation from which all other combinations are built.

The transition is: for each coin, for each amount from coin to target, dp[amount] += dp[amount - coin]. This says: for every way to make (amount - coin) using coins seen so far, we can extend that combination by adding one more of the current coin to reach amount. Because the outer loop is over coins (not amounts), each coin denomination contributes its combinations on top of the combinations already established by earlier denominations.

After processing all coins, dp[amount] holds the total number of combinations. The 1D approach works because dp[amount - coin] is always a smaller index, so it references a value that has already been updated in the current coin pass — exactly what the unbounded knapsack requires to allow the same coin to be used multiple times.

When the outer loop iterates over coins and the inner loop iterates over amounts, you are effectively asking: "given this new coin denomination, how many new combinations can be built by appending one of this coin to every combination that sums to (amount - coin) using only the coins processed so far?" The phrase "using only the coins processed so far" is the key: each coin denomination is introduced once, and the dp array is updated to reflect exactly the combinations achievable with that expanded set.

When the loops are reversed — outer over amounts, inner over coins — the question becomes: "for this target amount, how many ways can I reach it using any coin?" Since all coins are available at every amount step, the same set of coins can be combined in any order. [1, 2] and [2, 1] are both counted because when processing amount=3, you reach it via (amount=2, add coin=1) and via (amount=1, add coin=2), and both of those intermediate amounts were themselves reachable in multiple orders. This produces permutation counts, which is what Combination Sum IV deliberately wants.

The bottom line: outer=coins produces combination counts (Coin Change II); outer=amount produces permutation counts (Combination Sum IV). The recurrence dp[a] += dp[a - coin] is identical in both cases. The entire difference is loop structure. Mastering this distinction is one of the deepest insights in DP — a single swap of two for-loops changes the mathematical meaning of the computation from counting ordered sequences to counting unordered sets.

Start: dp = [1, 0, 0, 0, 0, 0]. Process coin=1: for a from 1 to 5, dp[a] += dp[a-1]. After coin=1: dp = [1, 1, 1, 1, 1, 1]. Every amount from 0 to 5 has exactly one combination using only 1-coins: [1], [1,1], [1,1,1], [1,1,1,1], [1,1,1,1,1]. This is correct — there is only one way to make any amount using only denomination 1.

Process coin=2: for a from 2 to 5, dp[a] += dp[a-2]. dp[2] += dp[0] → dp[2]=2 (ways: [1,1] and [2]). dp[3] += dp[1] → dp[3]=2 (ways: [1,1,1] and [1,2]). dp[4] += dp[2] → dp[4]=1+2=3 (ways: [1,1,1,1], [1,1,2], [2,2]). dp[5] += dp[3] → dp[5]=1+2=3 (ways: [1,1,1,1,1], [1,1,1,2], [1,2,2]). After coin=2: dp = [1, 1, 2, 2, 3, 3].

Process coin=5: for a from 5 to 5, dp[5] += dp[0] → dp[5]=3+1=4. The new combination is [5] itself. After coin=5: dp = [1, 1, 2, 2, 3, 4]. The answer dp[5]=4 corresponds to: [1,1,1,1,1], [1,1,1,2], [1,2,2], [5]. All four are distinct combinations, and no permutation duplicates appear because the coin=2 pass built on top of the coin=1 pass rather than reconsidering coin=1 in a new order.

Python implementation: def change(amount: int, coins: list[int]) -> int: dp = [0] * (amount + 1); dp[0] = 1; for coin in coins: for a in range(coin, amount + 1): dp[a] += dp[a - coin]; return dp[amount]. The outer loop is coins, inner is range(coin, amount+1) — range starts at coin because dp[a - coin] would be out of bounds for a < coin. The entire solution is 5 lines. Time O(amount × len(coins)), space O(amount). No sorting required.

Java implementation: public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; dp[0] = 1; for (int coin : coins) { for (int a = coin; a <= amount; a++) { dp[a] += dp[a - coin]; } } return dp[amount]; }. The Java version mirrors the Python exactly. Both use a single 1D array, both have the outer loop over coins and inner over amounts, and both rely on dp[0]=1 as the base case. The Java for-each loop over coins makes the structure identical to the Python for-in loop.

Comparing to Coin Change I: the only structural difference is the recurrence (dp[a] = min(dp[a], dp[a-coin]+1) vs dp[a] += dp[a-coin]) and the initialisation (dp[0]=0 with dp filled with infinity vs dp[0]=1 with dp filled with 0). Comparing to Combination Sum IV: the loops are swapped — outer=amount, inner=coins, and dp[0]=1 with dp[a] += dp[a-coin]. This side-by-side comparison clarifies how related problems share structure but differ in critical details.

Coin Change I (LeetCode 322) uses the same unbounded structure but minimises rather than counts: dp[i] = min(dp[i], dp[i - coin] + 1). It initialises dp with infinity (except dp[0]=0) and returns dp[amount] if finite, else -1. The loop order does not matter for minimisation because min() is commutative — swapping the loops still gives the correct minimum. This is why Coin Change I is often taught before Coin Change II even though II has a simpler recurrence.

Combination Sum IV (LeetCode 377) uses the same dp[a] += dp[a - coin] recurrence as Coin Change II but with outer=amount and inner=coins. It counts ordered sequences (permutations) where [1,2] and [2,1] are distinct. Understanding why the same recurrence with swapped loops produces a different mathematical quantity — combinations vs permutations — is the deepest conceptual bridge in the knapsack family and is commonly tested in senior engineer interviews.

Target Sum (LeetCode 494) and the 0/1 knapsack subset sum problems are bounded variants: each item is used at most once. They require a 2D DP table or careful backward iteration in a 1D array (iterating amounts from right to left to prevent double-counting). The unbounded variants (Coin Change I, Coin Change II, Combination Sum IV) use forward iteration. This forward-vs-backward inner loop direction is the structural signal that distinguishes bounded from unbounded knapsack in code.