MediumNeetCode150ArrayDynamic Programming
Coin Change II
Count combinations to make amount.
Examples
Input
amount = 5, coins = [1,2,5]
Output
4
Ways: 5, 2+2+1, 2+1+1+1, 1+1+1+1+1.
Constraints
- •
1 <= coins.length <= 300 - •
1 <= coins[i] <= 5000 - •
0 <= amount <= 5000
Approaches
Try all combinations.
CodeT: O(amount^n) | S: O(amount) stack
dp[j] = ways to make amount j.
CodeT: O(amount * len(coins)) | S: O(amount)
Same approach.
CodeT: O(amount * len(coins)) | S: O(amount)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Recursion | O(amount^n) | O(amount) stack | Try all combinations. |
| DP 1D | O(amount * len(coins)) | O(amount) | dp[j] = ways to make amount j. |
| DP Optimized | O(amount * len(coins)) | O(amount) | Same approach. |
Recursion
T: O(amount^n)S: O(amount) stack
Try all combinations.
DP 1D
T: O(amount * len(coins))S: O(amount)
dp[j] = ways to make amount j.
DP Optimized
T: O(amount * len(coins))S: O(amount)
Same approach.
Common Mistakes
Wrong loop order
Off-by-one
Not handling amount=0