Coin Change II
Given an array coinsamountamount
A combination ignores order: 1 + 2 + 2 and 2 + 1 + 2 count once. The limits are 1 <= coins.length <= 3001 <= coins[i] <= 50000 <= amount <= 5000
Example 1
Output: 4
Explanation: 5, 2 + 2 + 1, 2 + 1 + 1 + 1, and 1 + 1 + 1 + 1 + 1.
Example 2
Output: 0
Example 3
Output: 1
How to Think About It
Step 1: Count, do not minimize
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]akk
ways[k][a] = ways[k - 1][a] + ways[k][a - coin]
Step 3: Squash it to one row
Row kk - 1kdpkdp[a]adp[a - coin]
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]dp[a - coin]
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
Walkthrough
Example 1: amount = 5coins = [1, 2, 5]dp
| State | dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | dp[5] |
|---|---|---|---|---|---|---|
| Start | 1 | 0 | 0 | 0 | 0 | 0 |
| After coin 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| After coin 2 | 1 | 1 | 2 | 2 | 3 | 3 |
| After coin 5 | 1 | 1 | 2 | 2 | 3 | 4 |
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 = 3dp[5]dp[0]
Java Solution
The method keeps one array where dp[a]a
- The base case:
counts the empty combination. It is what makes a single coin equal to the amount count once, anddp[0] = 1 returns 1.amount = 0 - Starting the inner loop at
: smaller amounts cannot use this coin, so their counts stay as they are, andcoin never goes negative.a - coin - Upward order: because
increases,a already includes this coin, so a coin can be used many times. Going downward would allow each coin at most once.dp[a - coin] - Overflow in the middle: entries for amounts other than
can exceed theamount range. Javaint addition wraps around exactly, so the final entry is still correct whenever the true answer fits.int
The last point is not theoretical. With coins 2, 4, ..., 598 plus 4999 and amount = 4999dp[4998]
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
amounts with one addition each. At the limits that is 300 × 5000 = 1.5 × 10^6 additions.amount - Space: O(amount). One array of
integers replaces the full table of coins by amounts, because each row only reads itself and the row before it.amount + 1
To list the combinations themselves instead of counting them, see