DSA Coin Change II — Counting Ways

The problem

Coin Change II counts the combinations of coins that sum to a target amount. A combination is a multiset of coins, meaning a set of coins where repeats count but order does not.

Coins may repeat without limit. Each denomination in the input is distinct. Amount zero has exactly one combination, the empty choice of no coins.

cases = [
    ([1, 2, 5], 5, 4),
    ([1, 3, 4], 6, 4),
    ([1, 2], 5, 3),
    ([2], 3, 0),
    ([1, 2, 5], 0, 1),
]
for coins, amount, expected in cases:
    print("coins", coins, "amount", amount, "combinations:", expected)

Read the first row by listing its combinations. They are 5, 2 + 2 + 1, 2 + 1 + 1 + 1, and five 1 coins. Four combinations make 5.

Intuition: counting orderings is the trap

The first idea builds amounts one coin at a time, in any order. Each coin extends every smaller amount. That idea counts each ordering of the same coins as its own way.

coins = [1, 2]
amount = 5
dp = [0] * (amount + 1)
dp[0] = 1
for a in range(1, amount + 1):
    for coin in coins:
        if coin <= a:
            dp[a] += dp[a - coin]
print("orderings for 5:", dp[5])
print("combinations for 5:", 3)
print("the combinations:", ["2+2+1", "2+1+1+1", "1+1+1+1+1"])

The count 8 is correct for orderings. It is wrong for this problem. The coins 2, 2 and 1 appear in three different orders inside that count, and all three are one combination.

Brute force: recursion over coin types

The brute force decides coin type by coin type. For one type it either takes another copy or moves on to the next type. A call with nothing left to make is one finished combination.

calls = 0

def ways(idx, left, coins):
    global calls
    calls += 1
    if left == 0:
        return 1
    if idx == len(coins) or left < 0:
        return 0
    take = ways(idx, left - coins[idx], coins)
    skip = ways(idx + 1, left, coins)
    return take + skip

for amount in [5, 11]:
    calls = 0
    result = ways(0, amount, [1, 2, 5])
    print("amount", amount, "combinations:", result, "calls:", calls)

The recursion is correct, and it is wasteful. It recomputes the same pair of coin type and remaining amount many times. The call count grows from 47 to 193 while the amount roughly doubles. A table can store each pair once.

The optimal solution: one coin type at a time

The state is dp[a], the number of combinations that make amount a using only the coin types processed so far. That one sentence is the whole method.

The coin loop runs outside and the amount loop runs inside, upward. One coin type is fully added before the next type starts. Each combination is therefore built in one fixed coin order and counted once.

def count_ways(coins, amount):
    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]

cases = [
    ([1, 2, 5], 5, 4),
    ([1, 3, 4], 6, 4),
    ([1, 2], 5, 3),
    ([2], 3, 0),
    ([1, 2, 5], 0, 1),
]
for coins, amount, expected in cases:
    result = count_ways(coins, amount)
    print("coins", coins, "amount", amount, "->", result, "expected:", expected, "match:", result == expected)

All five cases match. Amount zero keeps its single empty combination, and the unreachable row answers 0. The companion Coin Change lesson counts the fewest coins for these coin sets. This lesson counts how many combinations exist.

Walkthrough: amount 5 with coins 1, 2 and 5

The walk grows the table one coin type at a time. Each printed row is the full table after one type is fully processed. The index of each entry is its amount.

coins = [1, 2, 5]
amount = 5
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
    for a in range(coin, amount + 1):
        dp[a] += dp[a - coin]
    print("after coin", coin, "table:", dp)
print("combinations for 5:", dp[5])

Read the answer off the last cell. After coin 2 the table already holds 3 combinations for amount 5. Coin 5 adds exactly one more, the single coin 5 itself.

Complexity

Time is O(coins times amount). Each coin type scans the amounts from its own value up to the target amount once.

Space is O(amount). One row holds a count for every amount up to the target.

for amount in [5, 10, 20]:
    dp = [0] * (amount + 1)
    dp[0] = 1
    updates = 0
    for coin in [1, 2, 5]:
        for a in range(coin, amount + 1):
            updates += 1
            dp[a] += dp[a - coin]
    print("amount", amount, "- updates:", updates, " combinations:", dp[amount])

The update count grows with the product of coins and amount. It stays in the dozens where the plain recursion needed hundreds of calls. The table trades a small row of memory for that gap.

Edge cases and pitfalls

An unreachable amount answers 0, not an error. A coin larger than the amount is simply never usable. No coins at all still leaves the empty combination for amount zero.

def count_ways(coins, amount):
    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]

print("no coins, amount 5:", count_ways([], 5))
print("no coins, amount 0:", count_ways([], 0))
print("coin too big:", count_ways([5], 3))
print("one coin type, repeated:", count_ways([2], 4))
print("odd amount, even coin:", count_ways([2], 3))

A repeated denomination is the quiet pitfall. The method treats each list entry as its own coin type, so a duplicated 1 inflates the count.

def count_ways(coins, amount):
    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]

print("coins [1, 1], amount 2:", count_ways([1, 1], 2))
print("coins [1], amount 2:", count_ways([1], 2))

Swapping the two loops is the other classic mistake. Amounts in the outer loop count orderings, as the intuition section showed. The loop order is not a style choice here. It decides what gets counted.