Coin Change II: Counting Combinations with DP

You are given an array of coin denominations and a target amount. Return the number of distinct combinations that sum to that amount. Each coin can be used an unlimited number of times, and order does not matter, so [1, 2] and [2, 1] count as the same combination.

This is LeetCode 518: Coin Change II, and it is one of the most important variations of the unbounded knapsack pattern. If you have solved Coin Change (minimum number of coins), this problem flips the question: instead of "how few coins do you need?" it asks "how many ways can you pick coins?"

That shift from minimization to counting changes the recurrence, and it introduces a subtle but critical detail about loop order.

Why this problem matters

Coin Change II teaches you the difference between counting combinations and counting permutations in DP. Both use the same 1D array, the same base case, and nearly identical recurrences. The only mechanical difference is the order of the two nested loops:

• Coins outer, amounts inner = combinations (order does not matter). This is Coin Change II.
• Amounts outer, coins inner = permutations (order matters). This is Combination Sum IV.

That single swap is the entire difference. Once you internalize it, you can pick the right loop order for any counting problem on sight.

The approach

Define dp[j] as the number of combinations that sum to amount j.

The base case: dp[0] = 1. There is exactly one way to make amount 0, which is to use no coins at all.

The recurrence: for each coin in the array, sweep through amounts from coin to amount. At each amount j, add dp[j - coin] to dp[j]. You are saying: "the number of ways to make j using coins up to this one includes all the ways to make j - coin, because I can extend each of those by adding one more of this coin."

Why does putting coins in the outer loop avoid counting permutations? Because you process each coin fully before moving to the next one. By the time you reach coin 2, all the "coin 1 only" ways are already baked in. You never go back and place coin 1 after coin 2. That constraint forces every combination to appear in exactly one canonical order.

The solution

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for j in range(coin, amount + 1):
            dp[j] += dp[j - coin]
    return dp[amount]

The outer loop iterates through each coin denomination. The inner loop sweeps from coin up to amount, accumulating ways. We return dp[amount] at the end.

That is the entire solution. Two nested loops, a 1D array, and a single base case.

Why loop order matters

This is the detail that trips people up in interviews. Let's compare the two loop orders side by side.

Coins outer (combinations, this problem):

for coin in coins:
    for j in range(coin, amount + 1):
        dp[j] += dp[j - coin]

Amounts outer (permutations, Combination Sum IV):

for j in range(1, amount + 1):
    for coin in coins:
        if coin <= j:
            dp[j] += dp[j - coin]

With coins outer, when you process coin 2, you only add ways that end with coin 2. You never revisit coin 1 after coin 2. So {1, 2} is counted once, and {2, 1} is not counted separately.

With amounts outer, at each amount j, you consider every coin independently. Nothing prevents you from building {1, 2} and {2, 1} as separate paths, so both get counted.

For coins = [1, 2, 5] and amount = 5:

• Combinations (coins outer): 4 ways. {5}, {2,2,1}, {2,1,1,1}, {1,1,1,1,1}
• Permutations (amounts outer): many more, because {1,2,2}, {2,1,2}, {2,2,1} are all counted separately

Complexity analysis

The outer loop runs len(coins) times. The inner loop runs up to amount times per coin. The DP array has amount + 1 entries. No recursion, no extra data structures.

The building blocks

Coin Change II is an unbounded knapsack counting problem. It belongs to the same family as Coin Change, but the optimization target is different:

• Coin Change (LeetCode 322): minimize the number of coins. dp[j] = min(dp[j], dp[j - coin] + 1).
• Coin Change II (LeetCode 518): count unordered combinations. dp[j] += dp[j - coin], coins outer.
• Combination Sum IV (LeetCode 377): count ordered permutations. dp[j] += dp[j - coin], amounts outer.

All three share the same skeleton. The recurrence operator changes (min vs. sum), and the loop order changes (coins outer vs. amounts outer). Once you see these as the same building block with different knobs, you can write any of them from memory.

The core pattern is: iterate over items and capacities, decide whether each item contributes to the current capacity, and combine results using the appropriate operator.

Edge cases to watch for

• amount = 0: return 1. There is exactly one way to make amount 0, the empty set.
• Empty coins array: if coins is empty and amount > 0, no coin is ever processed, so every dp[j] stays at 0. Return 0.
• Single coin that divides amount: coins = [3], amount = 9. The only combination is three 3s, so the answer is 1.
• Single coin that does not divide amount: coins = [3], amount = 7. No valid combination exists. Return 0.
• Large amount with small coins: the DP table can be large, but the algorithm remains O(amount * n) which handles LeetCode constraints comfortably.

From understanding to recall

You can trace the DP table right now and see why each cell has its value. The question is whether you can reproduce the solution from scratch in an interview, with someone watching, two weeks from now.

The part people forget is the loop order. Under pressure, it is easy to default to "amounts outer" without thinking, and accidentally count permutations instead of combinations. Spaced repetition builds the habit of pausing and asking: "does order matter in this problem?" If yes, amounts outer. If no, coins outer.

The unbounded knapsack pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling it in isolation, until the loop order question becomes reflexive, is much more effective than re-reading explanations each time.

Related posts

• Coin Change - The sibling problem that minimizes coin count instead of counting combinations. Same DP skeleton with min instead of +=.
• Combination Sum IV - Counts ordered permutations instead of unordered combinations. Comparing the two makes the loop order distinction crystal clear.
• Climbing Stairs - The gentlest intro to counting DP. Same "how many ways" question with a simpler transition.