Coin Change II

Coin Change II asks you to count the ways to make an amount, not to minimize coins. It is the cleanest introduction to the unbounded knapsack counting pattern — and to the subtle rule about which loop goes on the outside.

The slow way first

You could try to enumerate every combination with recursion — for each coin, decide how many of it to use, then recurse on the rest. Without memoization this explores an exponential number of branches and re-solves the same sub-amounts over and over. We want to count each sub-amount once.

The question to ask: how many ways are there to make amount a? If we knew that for every smaller amount, we could build up the answer. That is exactly what a dp array gives us.

The idea: build up a ways-to-make table

Let dp[a] be the number of combinations that make amount a. Start with dp[0] = 1 — there is exactly one way to make 0: use no coins. Then bring coins in one at a time. When we add a coin, any combination ending with that coin came from a combination making a - coin, so dp[a] += dp[a - coin].

The crucial detail: the coin loop is on the outside. Each coin is fully absorbed before the next one starts, so we never count 1+2 and 2+1 as different — only combinations, never permutations.

Walk through it

Step through the animation. After coin = 1, every dp[a] is 1 (only one way using all ones). Adding coin = 2 lets bigger amounts pick up extra combinations, and coin = 5 finally adds the single-coin way to make 5. The last cell settles on 4.

Pseudocode

dp = array of zeros, length amount + 1
dp[0] = 1                          # one way to make 0
for each coin in coins:            # coins on the OUTSIDE -> combinations
    for a from coin to amount:
        dp[a] = dp[a] + dp[a - coin]
return dp[amount]

The Python solution

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

• dp[a] holds the number of combinations that sum to a; we size it amount + 1 to index 0..amount.
• dp[0] = 1 seeds the recurrence — the empty combination makes 0.
• The outer loop over coins is what counts combinations rather than permutations.
• The inner loop starts at coin (smaller amounts cannot use this coin) and goes up to amount.
• dp[a] += dp[a - coin] folds in every combination that ends with one more of coin.

Complexity

We use a single dp array of size amount + 1, and each of its cells is touched once per coin, giving O(amount × number_of_coins) time and O(amount) space.

When this pattern shows up

Practice