14.21 Coin Change II

14.21.1 Problem Metadata

14.21.2 Description

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

14.21.3 Examples

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: There are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: The amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10]
Output: 1

14.21.4 Constraints

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

14.21.5 Solution - Dynamic Programming (Unbounded Knapsack)

14.21.5.1 Walkthrough

This problem is a classic Unbounded Knapsack variant where we need to count the number of combinations (not lc-permutations) to make up a target amount using an unlimited supply of coins.

Key Distinction - Combinations vs Permutations:

The problem asks for combinations, meaning [1,2] and [2,1] are considered the same way to make amount 3. This is crucial because: - Combinations: Order doesn’t matter → {1,2} is same as {2,1} - Permutations: Order matters → [1,2] is different from [2,1]

To ensure we count combinations (not lc-permutations), we iterate coins in the outer loop and amounts in the inner loop. This prevents counting the same combination multiple times with different orderings.

Core DP Strategy:

We use a 1D DP array where dp[i] represents the number of combinations to make amount i.

Recurrence Relation:

For each coin and each amount i >= coin:

dp[i] = dp[i] + dp[i - coin]

This means: - dp[i]: Current count of combinations for amount i (using previously processed coins) - dp[i - coin]: Count of combinations for the remaining amount after using one coin - We add these together because using the current coin gives us additional combinations

Base Case:

dp[0] = 1

There’s exactly one way to make amount 0: use no coins at all.

Visual Example: amount = 5, coins = [1, 2, 5]

Let’s trace through the algorithm step by step:

Initial State:

dp = [1, 0, 0, 0, 0, 0]
      ↑
   amount 0 = 1 way (use no coins)

Iteration 1: Process coin = 1

For each amount i from 1 to 5, update dp[i] += dp[i - 1]:

i=1: dp[1] += dp[0] → dp[1] = 0 + 1 = 1  (one 1)
i=2: dp[2] += dp[1] → dp[2] = 0 + 1 = 1  (two 1s)
i=3: dp[3] += dp[2] → dp[3] = 0 + 1 = 1  (three 1s)
i=4: dp[4] += dp[3] → dp[4] = 0 + 1 = 1  (four 1s)
i=5: dp[5] += dp[4] → dp[5] = 0 + 1 = 1  (five 1s)

dp = [1, 1, 1, 1, 1, 1]

After processing coin=1, we can make: - Amount 1: {1} → 1 way - Amount 2: {1,1} → 1 way - Amount 3: {1,1,1} → 1 way - Amount 4: {1,1,1,1} → 1 way - Amount 5: {1,1,1,1,1} → 1 way

Iteration 2: Process coin = 2

For each amount i from 2 to 5, update dp[i] += dp[i - 2]:

i=2: dp[2] += dp[0] → dp[2] = 1 + 1 = 2  (added {2})
i=3: dp[3] += dp[1] → dp[3] = 1 + 1 = 2  (added {2,1})
i=4: dp[4] += dp[2] → dp[4] = 1 + 2 = 3  (added {2,2} and {2,1,1})
i=5: dp[5] += dp[3] → dp[5] = 1 + 2 = 3  (added {2,2,1} and {2,1,1,1})

dp = [1, 1, 2, 2, 3, 3]

After processing coin=2, we can make: - Amount 2: {1,1}, {2} → 2 ways - Amount 3: {1,1,1}, {2,1} → 2 ways - Amount 4: {1,1,1,1}, {2,1,1}, {2,2} → 3 ways - Amount 5: {1,1,1,1,1}, {2,1,1,1}, {2,2,1} → 3 ways

Iteration 3: Process coin = 5

For each amount i from 5 to 5, update dp[i] += dp[i - 5]:

i=5: dp[5] += dp[0] → dp[5] = 3 + 1 = 4  (added {5})

dp = [1, 1, 2, 2, 3, 4]
      ↑              ↑
   base case    answer

Final Result: dp[5] = 4

The 4 combinations are: 1. {5} (one 5-coin) 2. {2, 2, 1} (two 2-coins, one 1-coin) 3. {2, 1, 1, 1} (one 2-coin, three 1-coins) 4. {1, 1, 1, 1, 1} (five 1-coins)

Why This Avoids Permutations:

By iterating coins in outer loop, we ensure each coin is considered in a fixed order. For example: - When processing coin=2, we only add combinations where 2 comes after all previously processed coins (coin=1) - This prevents counting {1,2} and {2,1} as different combinations

Counter-example (Wrong Approach):

If we swap loops (amounts outer, coins inner), we’d count lc-permutations instead:

// WRONG - counts lc-permutations
for (int i = 1; i <= amount; i++) {
    for (int coin : coins) {
        if (i >= coin) {
            dp[i] += dp[i - coin];
        }
    }
}

This would count [1,2] and [2,1] as different ways, giving incorrect results.

Key Insights:

  1. Outer loop = coins ensures combinations (not lc-permutations)
  2. Inner loop = amounts builds up solutions incrementally
  3. dp[i - coin] represents “what we can build if we use one more coin”
  4. Addition accumulates all ways to reach each amount
  5. Base case dp[0] = 1 enables the recurrence to work (identity element)

14.21.5.2 Analysis

  • Time Complexity: O(n × m)
    • n = amount (inner loop runs from coin to amount)
    • m = coins.length (outer loop processes each coin)
    • For each of the m coins, we update up to n DP states
    • Total operations: O(n × m)
  • Space Complexity: O(n)
    • DP array of size amount + 1
    • No additional data structures needed
    • Space-optimized: Uses 1D array instead of 2D (saves O(m × n) → O(n))

Why 1D Array Works:

The classic 2D formulation would be:

dp[coin_index][amount] = dp[coin_index-1][amount] + dp[coin_index][amount-coin]

But notice we only need the previous coin row and current coin row. By iterating coins in outer loop and processing amounts left-to-right, the 1D array automatically reuses previous results correctly.

14.21.5.3 Implementation Steps

  1. Initialize DP array:
    • Create dp[amount + 1] initialized to 0
    • Set dp[0] = 1 (base case: one way to make amount 0)
  2. Outer loop - Iterate through coins:
    • For each coin in coins[]
    • This ensures we count combinations (not lc-permutations)
  3. Inner loop - Iterate through amounts:
    • For each amount i from coin to amount (inclusive)
    • Start from coin because we can’t use this coin for amounts smaller than it
    • Update rule: dp[i] += dp[i - coin]
      • dp[i]: Current count (using previously processed coins)
      • dp[i - coin]: Ways to make the remaining amount after using one coin
      • Add because using current coin gives additional combinations
  4. Return: dp[amount] contains the total number of combinations

Why the loops are ordered this way: - Outer loop (coins): Ensures we consider coins in a fixed order - Inner loop (amounts): Builds up solutions for increasing amounts - Left-to-right inner loop: Allows reusing the same coin multiple times (unbounded)

14.21.5.4 Code - Java

class Solution {
    public int change(int amount, int[] coins) {
        // dp[i] = number of combinations to make amount i
        int[] dp = new int[amount + 1];

        // Base case: one way to make amount 0 (use no coins)
        dp[0] = 1;

        // Outer loop: iterate through coins (ensures combinations, not lc-permutations)
        for (int coin : coins) {
            // Inner loop: update all amounts that can use this coin
            for (int i = coin; i <= amount; i++) {
                // Add combinations from using this coin
                dp[i] += dp[i - coin];
            }
        }

        return dp[amount];
    }
}