Coin Change II

LeetCode 518: Coin Change II Solution & Explanation

Problem Overview

TL;DR: To count the number of combinations, use a 1D Dynamic Programming array where you iterate through each coin and update the ways to reach every amount from the coin's value up to the target.

The Coin Change II problem asks us to determine the number of distinct combinations of coins that sum up to a specific total amount. We are given an array of distinct coin denominations and an infinite supply of each coin. Unlike similar problems that ask for the minimum number of coins or specific permutations, LeetCode 518 specifically requires the count of unique combinations (where order does not matter).

This is a classic interview question that tests your understanding of the Unbounded Knapsack problem and the subtle differences in loop ordering within Dynamic Programming.

Brute Force Approach for Coin Change II

The naive approach involves using recursion to explore every possible combination of coins. We can define a recursive function that subtracts a coin's value from the current amount until the amount reaches 0.

To avoid counting permutations (e.g., treating 1 + 2 and 2 + 1 as different), we must pass an index to the recursive function to ensure we only consider coins at the current index or greater for subsequent calls.

Pseudo-code:

function countWays(amount, index, coins):
    if amount == 0: return 1
    if amount < 0 or index == length(coins): return 0
    
    // Option 1: Include current coin (stay at same index because infinite supply)
    include = countWays(amount - coins[index], index, coins)
    
    // Option 2: Skip current coin and move to next
    exclude = countWays(amount, index + 1, coins)
    
    return include + exclude

Why it fails: This approach has an exponential time complexity, roughly $O(2^{\text{amount} + \text{coins.length}})$. The recursion tree grows rapidly because the algorithm recalculates the same subproblems repeatedly (e.g., how many ways to make change for amount 5 using coins starting from index 1). For the given constraints (amount <= 5000), this results in a Time Limit Exceeded (TLE) error.

Algorithm Strategy: DP - 1D Array

We utilize a 1D array dp where dp[i] represents the number of ways to make the amount i.

1. Initialization:

   • Create a dp array of size amount + 1.
   • Set dp[0] = 1. This is the base case: there is exactly one way to make an amount of 0 (by choosing no coins).
   • All other indices are initialized to 0.

2. Iteration:

   • Outer Loop: Iterate through each coin c in the coins array. This step represents introducing a new denomination into our set of allowed coins.
   • Inner Loop: Iterate through the dp array indices i starting from c up to amount. We start at c because we cannot make change for an amount smaller than the coin itself.

3. State Transition:

   • Apply the recurrence relation: dp[i] += dp[i - c].
   • This means: "The new number of ways to make amount i equals the existing ways (without this coin) plus the ways to make amount i - c (using this coin at least once)."

4. Result:

   • Return dp[amount].

Execution Flow

Let's trace amount = 5, coins = [1, 2, 5].

1. Setup:

   • dp array of size 6: [1, 0, 0, 0, 0, 0] (Index 0 is 1, others 0).

2. Process Coin 1:

   • Iterate i from 1 to 5.
   • dp[1] += dp[0] → dp[1] = 1
   • dp[2] += dp[1] → dp[2] = 1
   • ...
   • dp[5] += dp[4] → dp[5] = 1
   • Array is now: [1, 1, 1, 1, 1, 1] (Only one way to make any amount using only 1s: 1+1...).

3. Process Coin 2:

   • Iterate i from 2 to 5.
   • dp[2] += dp[0] → 1 + 1 = 2 (Ways: 1+1, 2)
   • dp[3] += dp[1] → 1 + 1 = 2 (Ways: 1+1+1, 1+2)
   • dp[4] += dp[2] → 1 + 2 = 3 (Ways: 1s, 1+1+2, 2+2)
   • dp[5] += dp[3] → 1 + 2 = 3 (Ways: 1s, 1+1+1+2, 1+2+2)
   • Array is now: [1, 1, 2, 2, 3, 3].

4. Process Coin 5:

   • Iterate i from 5 to 5.
   • dp[5] += dp[0] → 3 + 1 = 4.
   • Array is now: [1, 1, 2, 2, 3, 4].

5. Final Output:

   • Return dp[5], which is 4.

Proof of Correctness

The algorithm is correct based on the principle of mathematical induction.

• Base Case: dp[0] = 1 is correct.
• Inductive Step: Assume dp[x] correctly stores the number of ways to make amount x using the first $k$ coins. When we introduce the $(k+1)$-th coin with value $C$, for any amount $j \ge C$, the total ways to form $j$ become the ways using only the first $k$ coins (already in dp[j]) plus the ways to form $j$ using the $(k+1)$-th coin at least once. Using the coin once leaves a remainder of $j-C$. Since we are iterating forward (Unbounded Knapsack), dp[j-C] has already been updated to include the $(k+1)$-th coin. Therefore, dp[j] += dp[j - C] correctly sums all combinations.
• Loop Order: By placing the coin loop outside, we ensure that for any combination involving multiple coin types, the coins are added in a fixed order (e.g., coin type 1, then coin type 2), preventing duplicate permutations.

Pattern Reuse Notes

The DP - 1D Array pattern used in LeetCode 518 is highly versatile.

• LeetCode 322: Coin Change: Uses the exact same loop structure (Coin outer, Amount inner), but instead of summing ways (+=), you take the minimum (min()) to find the fewest coins.
• LeetCode 377: Combination Sum IV: Uses the same recurrence dp[i] += dp[i-num], but swaps the loops (Amount outer, Coin inner) to count permutations instead of combinations.

Reference Implementation

C++ Solution for LeetCode 518

1class Solution {
2public:
3    int change(int amount, vector<int>& coins) {
4        // dp[i] represents the number of ways to make amount i
5        vector<int> dp(amount + 1, 0);
6        
7        // Base case: There is one way to make amount 0 (choose nothing)
8        dp[0] = 1;
9        
10        // Outer loop: Iterate through each coin
11        // This ensures we consider combinations, not permutations
12        for (int coin : coins) {
13            // Inner loop: Update dp table for amounts that can include this coin
14            for (int j = coin; j <= amount; j++) {
15                dp[j] += dp[j - coin];
16            }
17        }
18        
19        return dp[amount];
20    }
21};

Java Solution for LeetCode 518

1class Solution {
2    public int change(int amount, int[] coins) {
3        // dp[i] represents the number of ways to make amount i
4        int[] dp = new int[amount + 1];
5        
6        // Base case: There is one way to make amount 0
7        dp[0] = 1;
8        
9        // Iterate over each coin first to handle combinations
10        for (int coin : coins) {
11            // Update dp array for all amounts >= coin
12            for (int j = coin; j <= amount; j++) {
13                dp[j] += dp[j - coin];
14            }
15        }
16        
17        return dp[amount];
18    }
19}

Python Solution for LeetCode 518

1class Solution:
2    def change(self, amount: int, coins: List[int]) -> int:
3        # dp[i] represents the number of ways to make amount i
4        dp = [0] * (amount + 1)
5        
6        # Base case: One way to make amount 0
7        dp[0] = 1
8        
9        # Iterate over each coin (outer loop)
10        for coin in coins:
11            # Iterate through amounts starting from the coin value
12            for j in range(coin, amount + 1):
13                dp[j] += dp[j - coin]
14                
15        return dp[amount]