Coin Change II: Counting Combinations, Not Permutations

Coin change comes in two versions that look almost identical and are answered by different recurrences. The first asks for the fewest coins that make an amount. The second, coin change II, asks how many ways there are to make it. The second has a trap the first does not: the order of the two loops decides whether you count combinations or ordered sequences, and only one of them is the question. The code is six lines. Knowing why the loops go the way they do is the interview.

The problem it solves

Given coin denominations, each usable any number of times, and a target amount, count the distinct combinations of coins that add up to it. With coins 1, 2 and 5 and a target of 5 there are four:

• 5
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 and 1 + 2 + 1 + 1 are the same combination, so they count once. A recursive enumeration that branches on "which coin next?" explores every ordering, which is exponential and also counts the wrong thing unless it forces the coins into a fixed order.

The intuition

Build a table ways[a]: the number of combinations that make amount a using the coins introduced so far.

The base case is ways[0] = 1. There is exactly one way to pay nothing: take no coins. It is not a placeholder. Every complete combination ends, when you remove its coins one by one, at that empty payment, so every count in the table is built from it.

Introduce one coin at a time. When coin c arrives, every amount a from c upwards gains the combinations that make a - c, each extended with one more c. Going through amounts in increasing order means ways[a - c] may already include copies of c from this same pass, which is what lets a coin be used more than once. That is the unbounded-knapsack pattern: a single row filled left to right.

Why the coin loop must be outside. Once a coin's pass is finished, it is never revisited. So every combination is built with its coins in the order they were introduced, 1s first, then 2s, then 5s, and each combination is generated exactly once. Put the amount loop outside and the coin loop inside, and each amount chooses any coin as its last one, in any order. Then 1 + 2 and 2 + 1 are different paths into the table, and you are counting ordered sequences. That is a different, also well-known problem, and for coins 1, 2 and 5 it answers 9, not 4.

Watch it run

The animation fills one row per coin, with coins 1, 2 and 5 and a target of 5. It starts at ways[0] = 1: exactly one way to pay nothing, and every complete combination ends by landing on that cell. With the 1 on the table, each amount from 1 to 5 gains every way of making the amount one below it, so each becomes 0 + 1 = 1. With the 2 now on the table, amount 2 gains every way of making 0: 1 + 1 = 2. Amount 3 gains the ways of making 1: 1 + 1 = 2. Amount 4 gains the ways of making 2, 1 + 2 = 3, and amount 5 gains those of 3, 1 + 2 = 3. With the 5 on the table, amount 5 gains every way of making 0: 3 + 1 = 4. Four combinations, and each coin got one pass and was never revisited, so 1 + 2 and 2 + 1 could not be counted twice.

The code

The lesson's table, with the coin loop outside:

def change(amount, coins):
    ways = [0] * (amount + 1)
    ways[0] = 1                          # one way to pay nothing: take nothing
    for coin in coins:                   # coins outside: every mix counted once
        for a in range(coin, amount + 1):
            ways[a] += ways[a - coin]
    return ways[amount]

print(change(5, [1, 2, 5]))              # 4
print(change(3, [2]))                    # 0
print(change(10, [10]))                  # 1
print(change(0, [7]))                    # 1   the empty payment

The row after each coin's pass, matching the animation's three rows:

def rows(amount, coins):
    ways = [1] + [0] * amount
    for coin in coins:
        for a in range(coin, amount + 1):
            ways[a] += ways[a - coin]
        print(coin, ways)

rows(5, [1, 2, 5])
# 1 [1, 1, 1, 1, 1, 1]
# 2 [1, 1, 2, 2, 3, 3]
# 5 [1, 1, 2, 2, 3, 4]

The same table with the loops swapped counts ordered sequences instead:

def sequences(amount, coins):
    ways = [1] + [0] * amount
    for a in range(1, amount + 1):       # amounts outside: any coin can be last
        for coin in coins:
            if coin <= a:
                ways[a] += ways[a - coin]
    return ways[amount]

print(sequences(5, [1, 2, 5]))           # 9
print(sequences(3, [1, 2]), change(3, [1, 2]))   # 3 2   1+2 and 2+1 differ

Both against brute force on 2,000 random coin sets, where the brute force enumerates every multiset of coins, and separately every ordered sequence:

import random

def brute_combinations(amount, coins, i=0):
    if amount == 0:
        return 1
    if i == len(coins):
        return 0
    total, k = 0, 0
    while k * coins[i] <= amount:        # use coin i exactly k times, then move on
        total += brute_combinations(amount - k * coins[i], coins, i + 1)
        k += 1
    return total

def brute_sequences(amount, coins):
    if amount == 0:
        return 1
    return sum(brute_sequences(amount - c, coins) for c in coins if c <= amount)

random.seed(20)
ok = True
for _ in range(2000):
    coins = random.sample(range(1, 9), random.randint(1, 4))
    amount = random.randint(0, 14)
    ok &= change(amount, coins) == brute_combinations(amount, coins)
    ok &= sequences(amount, coins) == brute_sequences(amount, coins)
print(ok)                                # True

The complexity

• Time: O(n · A) for n coin types and amount A. Each coin makes one pass over at most A amounts.
• Space: O(A). One row, reused for every coin, because the new row only reads cells to its left in the same row.
• Compared with the fewest-coins version: the same table shape and the same cost; only the combining step changes, + of counts instead of min of coin counts.
• Large counts: the number of ways grows quickly with the amount. Python integers do not overflow; in fixed-width languages, check whether the question promises the answer fits.

Where it goes wrong

• Swapping the loops. Amounts outside, coins inside, counts orders: 9 instead of 4 for the lesson's example.
• Setting ways[0] = 0. Then nothing is ever added and every answer is 0.
• Iterating amounts downwards. That turns unlimited coins into one of each, the 0/1 knapsack rule, and undercounts.
• Reusing the fewest-coins recurrence. min answers a different question; counting needs a sum.
• Assuming 0 means "impossible" in the wrong direction. change(0, coins) is 1, the empty payment, even when no coin is small enough to use.

When it shows up in interviews

It usually follows the fewest-coins version, and the interviewer's real question is "why is the coin loop outside?" The swapped-loop problem, counting ordered sequences, is often asked right after, and so is the difference from the 0/1 knapsack, where the row is filled right to left. The family is listed under knapsack DP on the patterns cheat sheet.

How to say it in an interview

"I keep ways[a], the number of combinations that make a with the coins seen so far, starting from ways[0] = 1 for the empty payment. For each coin, I go through the amounts from that coin upwards and add ways[a - coin] to ways[a]. Going upwards lets a coin be reused within its own pass. The coin loop has to be outside: each coin is introduced once and never revisited, so every combination is built in one fixed order and counted once. With the loops swapped I would count ordered sequences instead. That is O(n · A) time and O(A) space."