⚡Flashcard Drill➔
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

  1. This is the unbounded knapsack counting problem: count combinations, not permutations.
  2. dp[a] is the number of ways to make amount a, with dp[0] = 1 for the empty combination.
  3. Process coins in the outer loop and amounts in the inner loop in ascending order, so each coin is reusable.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems