4.24.4 — Coin Change II

LeetCode 518 · Medium

The problem

Count the number of combinations of coins that make the amount. Coins are unlimited. Two combinations differ only if the counts differ, so [1,1,2] and [2,1,1] are the same combination.

amount = 5, coins = [1,2,5]   →  4
    5
    2 + 2 + 1
    2 + 1 + 1 + 1
    1 + 1 + 1 + 1 + 1

The pattern

Counting, so the operator is +. The state is the amount, and the twist is the word combination.

The clean way to avoid counting [1,2] and [2,1] separately is to fix an order: consider the coins one at a time, and once you have moved past a coin, never go back to it.

That gives a 2-D state — dp[i][a] = the number of ways to make amount a using only the first i coins — and the recurrence has the familiar take-it-or-leave-it shape:

dp[i][a] = \underbrace{dp[i-1][a]}_{\text{do not use coin } i} + \underbrace{dp[i][a - c_i]}_{\text{use coin } i \text{, possibly again}}

Note the second term keeps i, not i − 1, because coins are unlimited and you may use the same coin repeatedly.

Rolled to one array, the coin dimension disappears into the loop order.

The loop order, which is the entire problem

Python

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1                            # one way to make 0: take nothing

        for c in coins:                      # ← COINS OUTSIDE
            for a in range(c, amount + 1):   # ← amounts inside, ascending
                dp[a] += dp[a - c]

        return dp[amount]

TypeScript

function change(amount: number, coins: number[]): number {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;

  for (const c of coins) {
    for (let a = c; a <= amount; a++) {
      dp[a] += dp[a - c];
    }
  }

  return dp[amount];
}

Swap the two loops and you count permutations instead of combinations.

# COMBINATIONS — coins outside          # PERMUTATIONS — amounts outside
for c in coins:                          for a in range(1, amount + 1):
    for a in range(c, amount + 1):           for c in coins:
        dp[a] += dp[a - c]                       if c <= a: dp[a] += dp[a - c]

For amount = 3, coins = [1, 2]: the left gives 2 (1+1+1 and 1+2), the right gives 3 (it also counts 2+1 as different from 1+2).

Why the order decides it. With coins outside, coin 1 is fully processed before coin 2 is touched, so every combination is built in one fixed coin order and can only be counted once. With amounts outside, every coin is available at every amount, so the same multiset gets built in every possible sequence.

This is one of the most instructive loop-order lessons in the whole book, and it comes up constantly. When a counting DP gives you a number that is too large, this is the first thing to check.

The three loop rules, together

Collecting the three directions that appear across the knapsack family, because they are easy to confuse:

you want	loops
combinations, coins reusable	item outside, capacity ascending
permutations, coins reusable	capacity outside, item inside
each item once (0/1 knapsack)	item outside, capacity descending

• Ascending allows reuse, because dp[a - c] may already include coin c.
• Descending forbids it, because dp[a - c] still holds the value from before this coin — that is 4.23.12 Partition Equal Subset Sum.
• Item outside fixes an order and counts each multiset once.

Three lines, and they cover half a dozen problems.

Trace

amount = 5, coins = [1, 2, 5]

After coin 1: dp = [1,1,1,1,1,1] — exactly one way to make each amount with 1s.

After coin 2: dp = [1,1,2,2,3,3] — for example dp[4] = 3 from 1+1+1+1, 2+1+1, 2+2.

After coin 5: dp[5] += dp[0], giving dp[5] = 4 ✓.

Complexity

O(\text{amount} \times \text{coins}) time, O(\text{amount}) space.

Coin Change versus Coin Change II

Worth putting side by side, because they look almost identical:

	Coin Change (4.23.8)	Coin Change II
asks	fewest coins	how many combinations
operator	min	+
dp[0]	0 (zero coins)	1 (one empty way)
loop order	either works	coins must be outside

The loop order only matters for counting. With min, the answer does not depend on the order the coins are considered, because the minimum over a set is order-independent. With +, order changes what you are counting. That is the deep reason, and it is a good answer to "why does the order matter here but not there".

Where this goes next

• Combination Sum IV — despite the name, it counts permutations, so the loops go the other way round. Comparing the two makes the rule stick.
• Target Sum — reduces to a subset-count knapsack. 4.24.5.
• Number of Dice Rolls With Target Sum — bounded counts per item, so a third loop over how many of each.

What the interviewer will push on

"Why must the coin loop be outside?" To fix an order so each multiset is counted once. Give the amount = 3, coins = [1,2] example showing 2 against 3.

"Why dp[0] = 1?" There is exactly one way to make zero — use nothing. It is the seed every other count is built from.

"Why does the amount loop go upwards?" Coins are reusable. Downwards would make each coin usable once.

"How is this different from Coin Change?" min versus +, and the loop order only matters for the counting version.

"What if you wanted permutations?" Swap the loops.

One thing to volunteer: state the three loop rules as a set. It shows you see one family with three switches rather than several unrelated problems, and it is the most transferable thing on this page.

Next: 4.24.5 Target Sum — where the work is an algebraic reduction before any DP is written.