Dynamic Programming · 120Medium
Coin Change II
Given an array of distinct coin denominations and a target amount, return the number of distinct COMBINATIONS that make up that amount. Coins are unlimited. Order does not matter: 1+2 and 2+1 are the same combination.
Constraints
- 1 <= coins.length <= 300
- 1 <= coins[i] <= 5000
- 0 <= amount <= 5000
- All coin values are distinct.
Examples
change(5, [1, 2, 5]) -> 4 // 5, 2+2+1, 2+1+1+1, 1x5 change(3, [2]) -> 0 change(0, [7]) -> 1 // the empty combination change(1, [2]) -> 0 // smallest unreachable amount change(4, [1, 2]) -> 3 // 1x4, 2+1+1, 2+2 change(11, [1, 5, 10]) -> 4
Edge cases
- Amount 0 has exactly one combination — take nothing.
- Order does NOT matter; counting permutations is the classic wrong answer.
Show the target complexity (spoiler)
- Naive
- O(amount^coins) time — recurse over every sequence of coin choices, which counts
- Target
- O(coins * amount) time, O(amount) space — a 1-D DP where the coin loop is outermost, so each combination is counted once.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/09-dynamic-programming/120-coin-change-ii.js ./practice c 120