DP — Coin Change II
↗ LeetCode: Coin Change II · Medium · pattern chapter →
Count ways to make amount from coins (unlimited each, unordered).
Example 1 — amount=5, coins=[1,2,5] → 4Example 2 — amount=3, coins=[2] → 0Example 3 — amount=10, coins=[10] → 1
Constraints — 1 ≤ #coins ≤ 300; 1 ≤ amount ≤ 5000. Brute recursion is O(k^amount) — for amount=100, k=10 that's 10¹⁰⁰. DP is O(A · C) = 5·10³ · 300 = 1.5·10⁶.
Interview timer00:00
Approach 1 — Brute recursion enumerating combos
Intuition. At each recursion, either use coin c (stay at c) or skip to next. Terminate at amount=0 or exhaust coins.
int changeBrute(int amount, int[] coins) {
return dfs(amount, coins, 0);
}
int dfs(int rem, int[] coins, int idx) {
if (rem == 0) return 1;
if (rem < 0 || idx == coins.length) return 0;
return dfs(rem - coins[idx], coins, idx) + dfs(rem, coins, idx + 1);
}Complexity — Time exponential in amount/coin ratio; Space O(amount) stack. TLE past amount=25. In an interview say "memoize on (rem, idx) → O(A · C)."
Approach 2 — Unbounded knapsack counting (canonical)
Insight. dp[amt] = number of ways to make amt. Outer loop = coins, inner = amount. This ordering counts unordered combinations (each coin's contribution is decided once per outer iteration, so different orderings don't count separately).
Contrast. Swap loop order → counts ordered sequences → Combination Sum IV.
int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int c : coins)
for (int t = c; t <= amount; t++)
dp[t] += dp[t - c];
return dp[amount];
}Complexity — Time O(amount · |coins|); Space O(amount). Say aloud in an interview: "loop-order is the only thing that distinguishes 'count combinations' from 'count permutations' — same recurrence."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute recursion | Exponential | O(A) | Reference; TLE past A=25 |
| Unbounded knapsack | O(A · C) | O(A) | Canonical |
When to use which
- Unordered → outer coins.
- Ordered → outer amount.
- Min coins → different — see Coin Change.