LeetCode 518 · 2-D DP

Coin Change II, explained with a picture

Counting the ways to make change.

Medium2-D DP
▶ Watch it step by step

The problem

Given coin values and an amount, count how many different combinations of coins add up to the amount (unlimited coins of each value; order doesn’t matter).

Input:  amount = 5, coins = [1, 2, 5]
Output: 4   (5, 2+2+1, 2+1+1+1, 1+1+1+1+1)

Picture it

Picture boxes ₹0 … ₹amount, each counting the ways to make that amount. We bring in one coin type at a time. When coin c arrives, every box x gains the ways of box x − c (“use one more c”). Handling coins one type at a time is what stops 1+2 and 2+1 being counted twice.

How to recognise it

  • You must count the combinations that reach an exact total, not find the fewest coins.
  • Order does not matter: 1 + 2 and 2 + 1 are the same combination.
  • Each coin type can be used any number of times.
  • The same sub-question ("how many ways to make this smaller amount?") repeats.
  • An amount up to 5000 with up to 300 coin types makes listing every combination impractical.

Start with brute force

Go through the coin types in order. For each coin, either use one more copy of it, or move on to the next type for good. Count the ways that land exactly on zero.

def change_brute(amount, coins):
    def go(i, remaining):
        if remaining == 0:
            return 1
        if i == len(coins) or remaining < 0:
            return 0
        use = go(i, remaining - coins[i])     # take another copy of coin i
        skip = go(i + 1, remaining)           # never use coin i again
        return use + skip
    return go(0, amount)

Every call splits in two and the same (i, remaining) pairs come up again and again. With coin 1 and amount 5000 the recursion is thousands of levels deep and the number of calls grows exponentially in the number of distinct paths. Time is exponential in the worst case, and space is O(amount) for the recursion.

From brute force to the idea

  1. Find the waste. The pair (coin index, remaining amount) has at most 300 × 5000 possible values, but the recursion solves each of them many times.
  2. One box per amount. Let ways[x] be the number of combinations that make x. ways[0] = 1, because the empty combination makes 0.
  3. Add coin types one at a time. After handling coins c1..ck, ways[x] counts combinations using only those types. When coin c arrives, every combination for x - c becomes a combination for x by adding one copy of c, so ways[x] += ways[x - c].
  4. Loop amounts upwards. Going from c up to the amount lets ways[x - c] already include copies of c, which gives unlimited use of that coin.
  5. Keep coins on the outside. Because one type is finished before the next begins, each combination is built in only one order (all 1s, then 2s, and so on). That is what stops 1 + 2 and 2 + 1 being counted twice.

This is the key idea: a one-dimensional table of counts, filled one coin type at a time.

The key idea

ways[x] += ways[x − c], looping coins on the outside and amounts on the inside. O(amount × coins).

Python solution

def change(amount, coins):
    ways = [1] + [0] * amount
    for c in coins:                  # one coin type at a time: no reorderings
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceExponential: use or skip choices without sharing resultsO(amount): recursion depth
1-D table (shown code)O(amount × coins): one addition per coin per amountO(amount): one box per amount, which replaces the full coins × amount table

For the largest inputs that is about 1.5 million additions.

Edge cases

  • Amount 0: returns 1, the empty combination, even with no coins (change(0, []) is 1).
  • Amount above 0 and no coins: returns 0.
  • Impossible amounts (change(3, [2])): returns 0.
  • One coin equal to the amount (change(10, [10])): returns 1.
  • Coin larger than the amount: range(c, amount + 1) is empty, so the coin is ignored (change(5, [7]) is 0).
  • Coin order in the list: [1, 2, 5] and [5, 2, 1] both give 4.
  • Big counts: Python integers do not overflow, so no modulo is needed; the problem promises the result fits in 32 bits.

Common mistakes

  • Swapping the loops (amounts outside, coins inside). That counts ordered sequences, so change(5, [1, 2, 5]) becomes 9 instead of 4.
  • Setting ways[0] = 0, which makes every answer 0.
  • Looping amounts downwards, which allows each coin at most once instead of any number of times.
  • Mixing this up with "fewest coins" (Coin Change), which uses min instead of a sum.
Your turn: each coin at most once

Each coin in the list can be used at most once. Count the combinations that make the amount. For [1, 2, 3, 4, 5] and amount 5 the answer is 3 (5, 1+4, 2+3). Describe your approach, then write it if you like.

Compare with our answer

Keep the same table and the same outer loop over coins, but run the amounts downwards. Then ways[a - c] still holds the count from before this coin, so each coin is added at most once.

def change_once(amount, coins):
    ways = [1] + [0] * amount
    for c in coins:
        for a in range(amount, c - 1, -1):     # downwards: no reuse of c
            ways[a] += ways[a - c]
    return ways[amount]

change_once(5, [1, 2, 3, 4, 5]) is 3, change_once(10, [5]) is 0, and change_once(0, [1]) is 1. Time O(amount × coins), space O(amount).

A strong answer mentions: reversing the inner loop direction, why the old values are still available, and that equal coin values in the list would count as different coins.

Check what stuck

1. You need the number of different orders in which coins from [1, 2, 5] can add up to 5 (so 1 + 2 and 2 + 1 differ). Which change to the shown approach fits?

2. Why is the shown code O(amount × coins) rather than exponential?

3. A learner starts with ways = [0] * (amount + 1) and leaves everything else unchanged. What does change(5, [1, 2, 5]) return?

Score 60% or more and the lesson is marked complete.