Coin Change II
Problem Statement
You are given an integer amount and an array coins of distinct denominations. Return the number of combinations that make up that amount. You may use each coin denomination unlimited times. The order of coins inside a combination does not matter.
Input
A target amount and an array coins of positive, distinct denominations.
Output
An integer: the number of unordered coin combinations that sum to amount.
Constraints
- •
1 <= coins.length <= 300 - •
1 <= coins[i] <= 5000 - •
All values in coins are distinct - •
0 <= amount <= 5000 - •
The answer fits in a signed 32-bit integer
Examples
Example 1
amount = 5, coins = [1,2,5]
4Example 2
amount = 3, coins = [2]
0Example 3
amount = 10, coins = [10]
1Learning Objectives
- Model coin-combination counting as unbounded knapsack counting.
- Use coin-outer and amount-ascending loops to count each unordered combination once.
- Explain why amount-outer and coin-inner loops count permutations, not combinations.
- Contrast the counting recurrence with Coin Change minimisation.
Intuition
Coin Change II looks close to Coin Change, but the value stored in the DP table changes. We no longer want the fewest coins; we want the number of combinations.
A combination should not be counted again just because the same coins are written in a different order. The standard trick is to process coin types one at a time. After processing coin 1 and coin 2, the table represents combinations that use only those coin types. When coin 5 arrives, it appends one or more 5s to combinations that were already counted with earlier coins and current 5s.
The loop direction is still ascending because coins are unlimited. The loop order is the part that prevents permutations. If you scan amount outside and try every coin inside, then amount 3 with coins 1 and 2 counts 1 + 2 and 2 + 1 separately. That is the Combination Sum IV pattern, not this problem.
Common mistakes
- ×Using amount as the outer loop and counting ordered sequences instead of unordered combinations.
- ×Scanning amount descending, which prevents reusing the same coin and turns the problem into 0/1 counting.
- ×Initialising **dp[0]** to 0; there is exactly one way to make amount 0, by choosing no coins.
- ×Copying the Coin Change minimisation recurrence instead of adding counts.
State Definition
Let dp[a] be the number of combinations that form amount a using only the coin denominations processed so far. The answer is dp[amount] after all coins are processed.
State Transition
Base case: dp[0] = 1, the empty combination. For each coin, scan a from coin up to amount and add combinations that end with one more copy of this coin:
dp[a] = dp[a] + dp[a - coin]
The amount scan is ascending so dp[a - coin] may already include the current coin, enabling unlimited copies. The coin loop is outside so combinations are generated in coin-type order. This counts 1 + 2 + 2 once, while an amount-outer loop would count multiple coin orders like Combination Sum IV.
Solutions
Solution: 1D unbounded combination count
Keep one count array over amounts. For each coin type, sweep amounts upward and add the number of ways to make the remaining amount after taking that coin.
Step-by-step
- Initialise dp[0] = 1 because the empty selection forms amount 0.
- For each coin, scan amounts from coin to amount.
- Add dp[current - coin] into dp[current].
- Because the coin loop is outside, every combination is counted when its latest coin type is processed, not once per ordering.
- Return dp[amount].
O(coins.length · amount)
O(amount)
Each coin updates every amount at most once.
Java implementation
Dry Run
Sample input
amount = 5, coins = [1, 2, 5]. Track the combination counts for amounts 0 through 5.
| coin | amount scan | dp[0..5] after coin | new combinations for amount 5 |
|---|---|---|---|
| start | none | [1, 0, 0, 0, 0, 0] | No positive amount is reachable yet. |
| 1 | 1 up to 5 | [1, 1, 1, 1, 1, 1] | One combination: five 1 coins. |
| 2 | 2 up to 5 | [1, 1, 2, 2, 3, 3] | Add combinations using at least one 2: 2 + 1 + 1 + 1 and 2 + 2 + 1. |
| 5 | 5 up to 5 | [1, 1, 2, 2, 3, 4] | Add the single combination 5. |
The final value dp[5] = 4 counts unordered combinations. No separate row appears for 1 + 2 + 2 versus 2 + 1 + 2 because coin types were processed in a fixed order.
Complexity Analysis
The same O(coins.length · amount) shape appears in both Coin Change problems, but the recurrence and loop-order meaning are different: minimisation uses min, counting uses addition.
1D unbounded combination count
O(coins.length · amount)
O(amount)
Each coin updates every amount at most once.
Interview Tips
Be very explicit about combinations versus permutations. Say: coins outer prevents reordering duplicates; amount ascending permits unlimited copies. Then mention that reversing the loop nesting gives Combination Sum IV-style ordered counts.
Likely follow-ups
- How would you count ordered sequences instead of unordered combinations?
- What if each coin had a limited count?
- How would you reconstruct all combinations for a small amount?
- What changes if coin denominations are not distinct?
Similar Problems
Key Takeaways
- Coin Change II counts combinations, not minimum coins and not permutations.
- Unbounded reuse requires ascending amount iteration.
- Coin-outer loop order ensures each unordered combination is counted once.
- The base **dp[0] = 1** represents the empty combination.