Watch 10 video solutions for Coin Change II, a medium level problem involving Array, Dynamic Programming. This walkthrough by NeetCode has 184,384 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.
You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.
Example 1:
Input: amount = 5, coins = [1,2,5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10] Output: 1
Constraints:
1 <= coins.length <= 3001 <= coins[i] <= 5000coins are unique.0 <= amount <= 5000Problem Overview: Given a list of coin denominations and a target amount, compute how many unique combinations of coins can make that amount. Each coin can be used unlimited times, and combinations with different orderings count as the same result.
Approach 1: Dynamic Programming with 2D Array (O(n × amount) time, O(n × amount) space)
This approach models the problem similarly to an unbounded knapsack. Use a 2D DP table dp[i][a] where i represents the first i coin types and a represents the current amount. For each state, you either exclude the current coin (dp[i-1][a]) or include it (dp[i][a - coin]) because coins can be reused. Iterating through coins and amounts fills the table and ensures every combination is counted exactly once. This method is easy to reason about and helpful when learning dynamic programming transitions.
Approach 2: Dynamic Programming with 1D Array (O(n × amount) time, O(amount) space)
The optimized version collapses the 2D DP table into a single array dp[a] representing the number of ways to form amount a. Initialize dp[0] = 1 since there is one way to make zero amount. Iterate through each coin first, then iterate amounts from the coin value up to the target. Update using dp[a] += dp[a - coin]. Processing coins in the outer loop prevents counting permutations like [1,2] and [2,1] separately, which is a key detail in combination problems involving arrays. This version reduces memory usage significantly while keeping the same time complexity.
Recommended for interviews: The 1D dynamic programming approach is the expected solution. It demonstrates strong understanding of dynamic programming state transitions and space optimization. Starting with the 2D formulation shows clear reasoning about the recurrence, while reducing it to 1D shows practical optimization skills interviewers look for.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with 2D Array | O(n × amount) | O(n × amount) | Best for understanding the DP state transition and building intuition for combination counting problems. |
| Dynamic Programming with 1D Array | O(n × amount) | O(amount) | Preferred solution when memory optimization matters and the standard approach expected in coding interviews. |