Coin Change II (LeetCode 518)

The problem

You get an amount and a list of coin denominations coins (unlimited supply of each). Return the number of combinations of coins that add up to amount. Order does not matter: 1 + 2 and 2 + 1 are the same combination.

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

The four ways are 5, 2+2+1, 2+1+1+1 and 1+1+1+1+1.

How to think about it

Start with brute force. Recursively choose coins until the total hits amount. To avoid counting 1+2 and 2+1 separately, you’d force coins to be chosen in non-decreasing order. That works but is exponential, with the same (remaining amount, smallest allowed coin) states repeated.

The key insight: process one coin type at a time. Let dp[a] be the number of ways to make a using only the coins seen so far. When you add coin c, every way to make a - c (which may already use c) becomes a way to make a by adding one more c. So dp[a] += dp[a - c], for a from c upwards. Going upwards lets c be reused any number of times.

Loop order is the whole problem. With coins on the outside, every combination is built in a fixed coin order, so it is counted exactly once. If you swap the loops (amounts outside, coins inside), you count permutations: 1+2 and 2+1 both get added, and the answer for the example becomes 9 instead of 4.

Which pattern is this? 1-D DP, unbounded knapsack counting. The tell is “number of combinations to reach a total”, where order must not matter.

Approach

1. Make dp of size amount + 1 with dp[0] = 1 (one way to make 0: use nothing) and zeros elsewhere.
2. For each coin c, for each amount a from c to amount: dp[a] += dp[a - c].
3. Return dp[amount].

Solution

def change(amount, coins):
    dp = [1] + [0] * amount                       # dp[0] = 1: the empty combination
    for c in coins:                               # coins OUTSIDE: combinations, not orderings
        for a in range(c, amount + 1): dp[a] += dp[a - c]   # add one more coin c
    return dp[amount]
# change(5, [1,2,5]) -> 4

Dry run

For amount = 5, coins = [1, 2, 5], the dp array after each coin:

dp[5] = 4.

Complexity

• Time: O(amount · len(coins)). Each coin sweeps the amounts once.
• Space: O(amount). One array.

Edge cases and pitfalls

• amount = 0 returns 1 (the empty combination), even with no coins.
• No way to make it (amount = 3, coins = [2]) returns 0.
• Swapping the loops counts ordered sequences instead of combinations. Explain why your loop order is right.
• Iterating amounts downwards turns this into 0/1 knapsack (each coin used at most once), which is a different problem.

Related problems

• Coin Change (LeetCode 322): the same table, but the minimum count instead of the number of ways.
• Combination Sum (LeetCode 39): list the combinations themselves with backtracking.
• Partition Equal Subset Sum (LeetCode 416): subset sums where each item is used at most once.