Coin Change II

Given an array coins of distinct coin values and an integer amount, return the number of combinations of coins that add up to amount. You may use each coin value any number of times. If the amount cannot be made, return 0. This is LeetCode 518.

A combination ignores order: 1 + 2 + 2 and 2 + 1 + 2 count once. The limits are 1 <= coins.length <= 300, 1 <= coins[i] <= 5000 and 0 <= amount <= 5000. The answer is guaranteed to fit in a signed 32-bit integer.

Example 1
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: 5, 2 + 2 + 1, 2 + 1 + 1 + 1, and 1 + 1 + 1 + 1 + 1.
Example 2
Input: amount = 3, coins = [2]
Output: 0
Example 3
Input: amount = 10, coins = [10]
Output: 1

How to Think About It

Step 1: Count, do not minimize

Coin Change asks for the fewest coins, so it takes a minimum over choices. Here every valid choice counts, so the recurrence adds the counts instead. The hard part is counting each combination once and not once per ordering.

Step 2: Decide one coin value at a time

Put the coin values in a fixed order. For the first value, decide how many to use; then move to the second value and never come back. Every combination corresponds to exactly one sequence of such decisions, so nothing is counted twice.

Let ways[k][a] be the number of ways to make a with only the first k coin values. Either coin k is not used at all, or it is used at least once and one copy can be removed:

ways[k][a] = ways[k - 1][a] + ways[k][a - coin]

Step 3: Squash it to one row

Row k only reads row k - 1 at the same amount and row k at a smaller amount. Keep one array dp. Before coin k is processed, dp[a] holds the old row. Walking a upward, dp[a - coin] already holds the new row, which is what allows the same coin to be reused.

Step 4: Why the coin loop must be outside

With coins in the outer loop, every combination is built in the fixed coin order from Step 2, so it is counted once. Swap the loops, amounts outside and coins inside, and dp[a] becomes the sum of dp[a - coin] over all coins. That asks "which coin comes last?", and different last coins give different orderings of the same coins.

The swapped version therefore counts ordered sequences. For Example 1 it returns 9: 5, the 3 orders of 2 + 2 + 1, the 4 orders of 2 + 1 + 1 + 1, and 1 + 1 + 1 + 1 + 1. Counting orderings is a different problem, LeetCode 377 (Combination Sum IV).

This "process one item, sweep the capacity upward" pattern is the unbounded knapsack. The introduction to dynamic programming covers how a 2D table shrinks to one row.

Walkthrough

Example 1: amount = 5, coins = [1, 2, 5]. The table shows dp after each coin has been processed.

Statedp[0]dp[1]dp[2]dp[3]dp[4]dp[5]
Start100000
After coin 1111111
After coin 2112233
After coin 5112234

With only coin 1, each amount has one way. Coin 2 adds the ways that use at least one 2: for example dp[4] = 1 + dp[2] = 1 + 2 = 3, which is 1+1+1+1, 2+1+1 and 2+2. Coin 5 only changes dp[5], from 3 to 3 + dp[0] = 4.

Java Solution

The method keeps one array where dp[a] counts the combinations for amount a using the coins processed so far, and adds one coin value at a time.

  • The base case: dp[0] = 1 counts the empty combination. It is what makes a single coin equal to the amount count once, and amount = 0 returns 1.
  • Starting the inner loop at coin: smaller amounts cannot use this coin, so their counts stay as they are, and a - coin never goes negative.
  • Upward order: because a increases, dp[a - coin] already includes this coin, so a coin can be used many times. Going downward would allow each coin at most once.
  • Overflow in the middle: entries for amounts other than amount can exceed the int range. Java int addition wraps around exactly, so the final entry is still correct whenever the true answer fits.

The last point is not theoretical. With coins 2, 4, ..., 598 plus 4999 and amount = 4999, the true dp[4998] needs 171 bits, yet the method returns the correct answer 1. A common mistake is to put the amount loop outside and the coin loop inside; Example 1 then returns 9 instead of 4, because each ordering is counted.

Java
public class CoinChangeII {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];   // dp[a]: combinations that make a with the coins so far
        dp[0] = 1;                         // the empty combination
        for (int coin : coins) {           // coins outside: each combination is built in one order
            for (int a = coin; a <= amount; a++) {
                dp[a] += dp[a - coin];     // dp[a - coin] may already use this coin
            }
        }
        return dp[amount];
    }
}

Complexity

  • Time: O(amount × number of coins). The outer loop runs once per coin value, and the inner loop sweeps at most amount amounts with one addition each. At the limits that is 300 × 5000 = 1.5 × 10^6 additions.
  • Space: O(amount). One array of amount + 1 integers replaces the full table of coins by amounts, because each row only reads itself and the row before it.

To list the combinations themselves instead of counting them, see Combination Sum, which uses backtracking with the same "never go back to an earlier value" rule.