NeetCode #721LC-518Medium2-D Dynamic ProgrammingNC 150NC 250
← Back to All Problems#721 · #518 · Coin Change II(零钱兑换 II)
📌 Problem Statement & Constraints
Given an integer array
coins and an integer amount, return the number of combinations that make up amount using an unlimited supply of each coin. Constraints: 1 <= coins.length <= 300, 1 <= coins[i] <= 5000, 0 <= amount <= 5000. The answer fits in a signed 32-bit integer.💡 Core Algorithmic Approaches
- This is the unbounded knapsack counting problem: count combinations, not permutations.
dp[a]is the number of ways to make amounta, withdp[0] = 1for the empty combination.- Process coins in the outer loop and amounts in the inner loop in ascending order, so each coin is reusable.
- The loop order is exactly what prevents counting the same multiset in different orders.
💻 Benchmark Python3 Implementation
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1 # one way to make zero
for c in coins: # coins outer -> combinations
for a in range(c, amount + 1):
dp[a] += dp[a - c] # ascending -> c is reusable
return dp[amount]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(amount * number of coins): one pass over the 2-D state space.
💾 Space Complexity
O(amount): one DP array.
⚠️ Interview Pitfalls & Follow-ups
- Swapping the loop order: putting amounts outside and coins inside counts permutations instead of combinations.
- Iterating amounts in descending order: that treats each coin as usable once, which is the 0/1 knapsack; unbounded coins need ascending order.
- Forgetting
dp[0] = 1: the empty combination is the base case. - Confusing this with Coin Change (322): that problem minimises the number of coins, while this one counts combinations.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.