Coin Change II

Description

Coin Change II

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.

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

Constraints:

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

Approach

• the loop is reversed wrt to 8. Coin Change because we are calculating combination instead of permutation
• O(n*amount), O(amount)

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
 
        for (int coin: coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin];
            }
        }
 
        return dp[amount];
    }
}

Primary Approach: 1D Space-Optimized Dynamic Programming ($O(N\times \text{amount})$ Time, $O(\text{amount})$ Space)

Intuition

To solve 518. Coin Change II, we use the Unbounded Knapsack formulation. Define dp[i] as the number of combinations to make up amount i:

1. Base Case: dp[0] = 1 because there is exactly 1 way to make an amount of 0 (by choosing no coins). All other dp entries start at 0.
2. Outer Loop over Coins: Iterating through coins in the outer loop guarantees that coins are considered in a fixed order, counting combinations (where order does not matter, e.g., [1, 2] is identical to [2, 1]).
3. Transition: For each coin and for each amount i from coin to amount:

$\text{dp}[i]=\text{dp}[i]+\text{dp}[i-\text{coin}]$

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1; // 1 way to make amount 0 (using no coins)
 
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
 
        return dp[amount];
    }
}
 

Complexity

• Time Complexity: $O(N\times \text{amount})$ — Where $N$ is the number of coins and $\text{amount}$ is the target value.
• Space Complexity: $O(\text{amount})$ — 1D DP array of size $\text{amount}+1$.

---

Alternative Approach: 2D Unbounded Knapsack DP ($O(N\times \text{amount})$ Time, $O(N\times \text{amount})$ Space)

Intuition

Define dp[i][j] as the number of ways to make amount j using a subset of the first i coins:

1. Exclude Coin i: Take dp[i - 1][j] (ways to form amount j without using the current coin).
2. Include Coin i: If $j\ge \text{coins}[i-1]$, add dp[i][j - coins[i - 1]] (since we can reuse the same coin infinitely, we look at row i rather than row i - 1).

$\text{dp}[i][j]=\text{dp}[i-1][j]+(\text{if }j\ge \text{coin}\text{ then }\text{dp}[i][j-\text{coin}]\text{ else }0)$

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
 
        // Base case: 1 way to make amount 0 with any prefix of coins
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
 
        for (int i = 1; i <= n; i++) {
            int coin = coins[i - 1];
            for (int j = 1; j <= amount; j++) {
                // Exclude current coin
                dp[i][j] = dp[i - 1][j];
 
                // Include current coin (unbounded reuse uses row i)
                if (j >= coin) {
                    dp[i][j] += dp[i][j - coin];
                }
            }
        }
 
        return dp[n][amount];
    }
}
 

Complexity

• Time Complexity: $O(N\times \text{amount})$ — Calculates transitions across all states.
• Space Complexity: $O(N\times \text{amount})$ — 2D table storing subproblem results.

---

Key Interview Discussion Points

• Combinations vs. Permutations:
  • Outer loop = coins, Inner loop = amount: Counts combinations (Coin Change II). Order does not matter, preventing duplicate groupings like 1 + 2 and 2 + 1.
  • Outer loop = amount, Inner loop = coins: Counts permutations (Combination Sum IV).
• 0-1 Knapsack vs. Unbounded Knapsack:
  • In 0-1 Knapsack, inner loops run backward (amount down to coin) to avoid using an item multiple times.
  • In Unbounded Knapsack, inner loops run forward (coin up to amount), intentionally enabling repeated coin usage.

---

Easy Memory Rule

“Outer Loop = Coins $\to$ Counts Combinations | Inner Loop Forward $\to$ Infinite Supply!”