Coin Change II — Counting Combinations with Unbounded Knapsack DP

Problem Statement#

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 in a signed 32-bit integer.

Constraints:

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• All values of coins are unique.
• 0 <= amount <= 5000

Example 1:

Input:  coins = [1, 2, 5], amount = 5
Output: 4
Explanation: Four combinations: 5, 2+2+1, 2+1+1+1, 1+1+1+1+1.
             Note: 2+1+1+1 and 1+2+1+1 are the SAME combination — order does not matter.

Example 2:

Input:  coins = [2], amount = 3
Output: 0
Explanation: Cannot make 3 with only coins of denomination 2.

Example 3:

Input:  coins = [10], amount = 10
Output: 1
Explanation: Only one combination: a single coin of denomination 10.

Why This Problem Matters#

Coin Change II (LeetCode 518) is the counting sibling of Coin Change (LC 322). While LC 322 asks "minimum coins to reach the amount," LC 518 asks "how many distinct combinations reach the amount?" The underlying DP structure is similar, but the operator changes (count instead of minimize) and — critically — the loop order is different.

Amazon and Google interviewers use this problem to test whether candidates truly understand the unbounded knapsack framework, specifically the distinction between:

• Combinations (order does not matter, e.g., 2+1 = 1+2): coins outer loop
• Permutations (order matters): amounts outer loop

Getting this distinction right — and being able to explain why — separates candidates who memorize DP templates from those who internalize the logic.

The Core Insight#

Define dp[i] as the number of distinct combinations of coins that sum to amount i.

Base case: dp[0] = 1 — there is exactly one combination that sums to 0: the empty combination.

Recurrence: For each coin c, and for each amount i >= c: dp[i] += dp[i - c]

This says: "the number of combinations summing to i includes all combinations summing to i - c, each augmented by one additional coin c."

The critical loop order insight:

If you iterate amounts in the outer loop and coins in the inner loop:

for i in range(1, amount + 1):        # amounts outer
    for c in coins:                    # coins inner
        if c <= i:
            dp[i] += dp[i - c]

This counts permutations (ordered sequences). For coins = [1, 2], amount = 3: it counts 1+2 and 2+1 as different — giving 4 instead of 3.

If you iterate coins in the outer loop and amounts in the inner loop:

for c in coins:                        # coins outer
    for i in range(c, amount + 1):    # amounts inner
        dp[i] += dp[i - c]

This counts combinations (unordered sets). Each coin is "committed" before we count its contributions, so we never count 1+2 and 2+1 separately.

Why: When coins are in the outer loop, by the time we process coin c, all combinations using only previous coins are already fixed. Coin c can only be added to those existing combinations — it cannot be interleaved with earlier coins in ways that create new orderings.

Building the DP Solution#

Step 1 — Naive Recursion with Ordering Parameter#

# Python — naive recursion, exponential — illustrative only
def change(amount, coins):
    def dp(remaining, coin_idx):
        """Count combinations using coins[coin_idx:] summing to remaining."""
        if remaining == 0:
            return 1
        if remaining < 0 or coin_idx == len(coins):
            return 0
        # Either skip this coin or use it (can reuse: stay at coin_idx)
        return dp(remaining - coins[coin_idx], coin_idx) + dp(remaining, coin_idx + 1)
    return dp(amount, 0)

// JavaScript — naive recursion
function change(amount, coins) {
    function dp(remaining, idx) {
        if (remaining === 0) return 1;
        if (remaining < 0 || idx === coins.length) return 0;
        return dp(remaining - coins[idx], idx) + dp(remaining, idx + 1);
    }
    return dp(amount, 0);
}

Step 2 — Top-Down Memoization (O(amount * n) time, O(amount * n) space)#

The state is (remaining, coin_index) — two dimensions:

# Python — top-down memoization
from functools import lru_cache
 
class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        @lru_cache(maxsize=None)
        def dp(remaining: int, idx: int) -> int:
            if remaining == 0:
                return 1
            if remaining < 0 or idx == len(coins):
                return 0
            return dp(remaining - coins[idx], idx) + dp(remaining, idx + 1)
 
        return dp(amount, 0)

// JavaScript — top-down memoization
var change = function(amount, coins) {
    const memo = new Map();
 
    function dp(remaining, idx) {
        if (remaining === 0) return 1;
        if (remaining < 0 || idx === coins.length) return 0;
        const key = `${remaining},${idx}`;
        if (memo.has(key)) return memo.get(key);
        const result = dp(remaining - coins[idx], idx) + dp(remaining, idx + 1);
        memo.set(key, result);
        return result;
    }
 
    return dp(amount, 0);
};

Step 3 — Bottom-Up Tabulation (O(amount * n) time, O(amount) space)#

The 1D optimization: by iterating coins outer, amounts inner, we compress the 2D state to a 1D table:

# Python — bottom-up tabulation (combinations order)
class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1  # One way to make 0: use no coins
 
        for c in coins:                          # coins outer loop
            for i in range(c, amount + 1):       # amounts inner loop
                dp[i] += dp[i - c]
 
        return dp[amount]

// JavaScript — bottom-up tabulation
var change = function(amount, coins) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
 
    for (const c of coins) {                     // coins outer loop
        for (let i = c; i <= amount; i++) {      // amounts inner loop
            dp[i] += dp[i - c];
        }
    }
 
    return dp[amount];
};

Optimized Solution#

The tabulation above is already the optimized solution — O(n * amount) time, O(amount) space:

# Python — final solution
class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for c in coins:
            for i in range(c, amount + 1):
                dp[i] += dp[i - c]
        return dp[amount]

// JavaScript — final solution
var change = function(amount, coins) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (const c of coins) {
        for (let i = c; i <= amount; i++) {
            dp[i] += dp[i - c];
        }
    }
    return dp[amount];
};

Visual Dry Run#

Input: coins = [1, 2, 5], amount = 5

Start: dp = [1, 0, 0, 0, 0, 0]

After processing coin = 1:

Combinations using only 1s: {1+1+1+1+1} for amount 5.

After processing coin = 2:

Combinations using 1s and 2s for amount 5: {1+1+1+1+1, 2+1+1+1, 2+2+1}.

After processing coin = 5:

Final combinations: {1+1+1+1+1, 2+1+1+1, 2+2+1, 5}. Answer = 4.

Complexity Analysis#

Common Mistakes#

1. Reversing the loop order — counting permutations instead of combinations. The single most common error. Coins outer, amounts inner = combinations (LC 518). Amounts outer, coins inner = permutations (LC 377 Combination Sum IV). Never mix them up.

2. Initializing dp[0] = 0. There is exactly one way to make amount 0: use no coins. dp[0] must be 1. Without this, the entire dp array stays 0.

3. Starting the inner loop at 0 instead of c. When i < c, coin c cannot be used (it exceeds the remaining amount). Starting at i = c avoids checking the c <= i condition on every iteration.

4. Confusing this with the permutations variant. LC 377 Combination Sum IV asks for the number of ordered sequences (permutations). It uses amounts outer, coins inner. LC 518 uses the opposite.

5. Not checking if amount = 0. When amount = 0, the answer is 1 (empty combination). The code returns dp[0] = 1 correctly without any special handling.

6. Forgetting that coins can be reused. This is unbounded knapsack — each coin can appear multiple times. In the 0/1 knapsack, iterate amounts in reverse to prevent reuse. Here, forward iteration allows reuse.

Interview Tips#

Explain the loop order before writing code. This is the crux of the problem. Say: "To count combinations without counting permutations, I put coins in the outer loop. By the time I process coin c, all ways using previous coins are finalized — so c can only extend existing combinations, not create new orderings."

Contrast with Coin Change I. "Coin Change minimizes count — dp[i] = min(dp[i-c] + 1). Coin Change II counts combinations — dp[i] += dp[i-c]. Same recurrence structure, different operator."

Contrast with Combination Sum IV (LC 377). "If the problem asked for the number of ordered ways (permutations), I would put amounts in the outer loop and coins in the inner loop. That is LC 377."

Show the small example trace. Walking through coins = [1, 2], amount = 3 with both loop orders (getting 3 for combinations and 4 for permutations) is a powerful way to demonstrate the distinction.

Follow-up Questions#

Q: What if you wanted ordered combinations (permutations) instead? Swap the loops: amounts outer, coins inner. This is Combination Sum IV (LC 377).

Q: What if each coin can only be used once (0/1 knapsack)? Iterate the amounts array in reverse (right to left) in the inner loop: for i in range(amount, c-1, -1): dp[i] += dp[i-c]. Reverse iteration prevents using the same coin twice in the current pass.

Q: What if you need to output all actual combinations, not just the count? Use DFS/backtracking to enumerate: recursively try using each coin from the current index onward, subtract from the remaining amount, and recurse. Collect all paths that reach 0.

Q: What if the number of ways is astronomically large? Return the count modulo a prime (commonly 10^9 + 7). The DP structure is unchanged — just add % MOD to each update.

Q: What if coins can be negative? Negative coin denominations would mean the problem becomes unbounded in the negative direction. In practice, coins are positive. With negative denominations, the problem is ill-defined without an additional constraint on the number of coins used.

Key Takeaways#

• Define dp[i] as the number of combinations summing to amount i. Base case: dp[0] = 1.
• The recurrence is dp[i] += dp[i - c] for each coin c <= i.
• The loop order is everything: coins outer + amounts inner = combinations (LC 518). Amounts outer + coins inner = permutations (LC 377).
• Coins can be reused (unbounded), so iterate amounts forward in the inner loop.
• Time O(n * amount), Space O(amount) — the gold standard for this problem.
• Distinguishing combinations from permutations by loop order is one of the most tested knapsack insights in FAANG interviews.