#518
Coin Change II
Medium Unbounded knapsack (count combinations)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count the combinations of coins (unlimited supply) that add up to amount. Order doesn't matter.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: how many combinations make the amount?
Why this works: loop coins outside, amounts inside, so each combination is counted once (order doesn't matter).
Example: amount 5, coins [1, 2, 5]
5, 2+2+1, 2+1+1+1, 1×5 → 4✦Hints open one at a time
Loop over coins on the outside and amounts on the inside — that counts combinations, not orderings.
ways[a] += ways[a − coin], with amounts going upwards (coins can repeat).
↗Approach
ways[0] = 1. For each coin, for a from coin to amount, add ways[a − coin].
</>Solution (Java)
class Solution {
public int change(int amount, int[] coins) {
int[] ways = new int[amount + 1];
ways[0] = 1;
for (int c : coins) { // coins outside: combinations
for (int a = c; a <= amount; a++) {
ways[a] += ways[a - c];
}
}
return ways[amount];
}
}!Common mistake
Swapping the loops, which counts 1+2 and 2+1 as different (that's a different problem).
Complexity
- Time: O(amount · coins).
- Space: O(amount).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon