Coin Change II: Count Combinations That Make an Amount

Problem

You are given distinct positive coin values and a target amount, with an unlimited supply of each coin. Return the number of different combinations of coins that add up to the amount. Combinations ignore order: 1 + 2 and 2 + 1 are the same. An amount of 0 has exactly one combination (use no coins).

This is widely known as LeetCode 518, “Coin Change II”. Coin Change asks for the fewest coins instead, and Combination Sum lists the combinations.

Assume up to 300 coin types, an amount up to 5,000, and an answer that fits in a 32-bit signed integer.

Examples

coins [1, 3], amount 4     -> 2   (1+1+1+1, 1+3)
coins [2, 3, 5], amount 8  -> 3   (2+2+2+2, 2+3+3, 3+5)
coins [4], amount 7        -> 0   (unreachable)
coins [6, 9], amount 0     -> 1   (the empty combination)

Approach 1: plain recursion with a coin index

Fixing the coin order (only use coins at or after index i) is what prevents counting reorderings.

def change_recursive(amount, coins):
    def go(i, rest):
        if rest == 0:
            return 1
        if i == len(coins) or rest < 0:
            return 0
        return go(i, rest - coins[i]) + go(i + 1, rest)   # use coin i again, or move on
    return go(0, amount)

Exponential without memoisation.

Approach 2: optimal, unbounded knapsack counting

State, recurrence and base cases

• State: ways[i][a] = combinations making amount a with the first i coin types.
• Recurrence: ways[i][a] = ways[i - 1][a] + (ways[i][a - c] if a >= c else 0) with c = coins[i - 1]. The second term uses the same row i, which is what allows reuse.
• Base cases: ways[i][0] = 1 for every i; ways[0][a] = 0 for a above 0.
• Answer: the last row, column amount.

Filled table for coins [2, 3, 5], amount 8

coins used	a=0	1	2	3	4	5	6	7	8
none	1	0	0	0	0	0	0	0	0
2	1	0	1	0	1	0	1	0	1
2, 3	1	0	1	1	1	1	2	1	2
2, 3, 5	1	0	1	1	1	2	2	2	3

Memoised

from functools import lru_cache

def change_memo(amount, coins):
    @lru_cache(maxsize=None)
    def go(i, rest):
        if rest == 0:
            return 1
        if i == len(coins) or rest < 0:
            return 0
        return go(i, rest - coins[i]) + go(i + 1, rest)
    return go(0, amount)

Bottom-up 2D

def change_table(amount, coins):
    ways = [[0] * (amount + 1) for _ in range(len(coins) + 1)]
    for i in range(len(coins) + 1):
        ways[i][0] = 1
    for i in range(1, len(coins) + 1):
        c = coins[i - 1]
        for a in range(1, amount + 1):
            ways[i][a] = ways[i - 1][a] + (ways[i][a - c] if a >= c else 0)
    return ways[-1][amount]

Space optimised (1D)

def change(amount, coins):
    ways = [1] + [0] * amount
    for c in coins:                       # coins outside: combinations
        for a in range(c, amount + 1):    # upwards: coin c may be reused
            ways[a] += ways[a - c]
    return ways[amount]

Why the loop order matters

With coins in the outer loop, every combination is built in the fixed coin order, so each multiset is counted once. If the amount loop is outside and the coin loop inside, ways[a] sums over “which coin came last”, which counts ordered sequences: 1 + 3 and 3 + 1 become different.

def count_sequences(amount, coins):
    ways = [1] + [0] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                ways[a] += ways[a - c]
    return ways[amount]

Complexity

O(k * A) time; O(k * A) space for 2D, O(A) for 1D.

Tests

for fn in (change, change_table, change_memo, change_recursive):
    assert fn(4, [1, 3]) == 2
    assert fn(8, [2, 3, 5]) == 3
    assert fn(7, [4]) == 0                         # unreachable
    assert fn(0, [6, 9]) == 1                      # zero amount
    assert fn(0, []) == 1
    assert fn(3, []) == 0                          # no coins
    assert fn(5, [5]) == 1                         # single coin

# Sequences versus combinations
assert count_sequences(4, [1, 3]) == 3            # 1111, 13, 31
assert change(4, [1, 3]) == 2

import random
random.seed(20)
for _ in range(60):
    cs = random.sample(range(1, 10), random.randint(1, 4))
    amt = random.randint(0, 20)
    assert change(amt, cs) == change_recursive(amt, cs) == change_table(amt, cs)

Edge cases and pitfalls

• Wrong loop order counts permutations, the most common bug in this question.
• Downward amount loop turns it into “each coin at most once”.
• Amount 0 has one combination, even with no coins.
• Large counts can overflow in fixed-width languages; Python handles big integers.

Where this shows up in data engineering

Counting the ways to compose a quantity from fixed units is a capacity-planning question: how many distinct mixes of instance sizes give exactly the required number of cores. More important in interviews is the loop-order insight, because the same “combinations versus sequences” distinction appears when you count distinct sets of events versus ordered event paths.