27. Coin Change 2 (Combination Count)

Difficulty:MediumPattern:Unbounded Knapsack DPTime:O(amount * n)Space:O(amount)

Given an integer array coins and an integer amount, return the number of combinations that make up that amount.

How It Works & Algorithmic Design

Solves using Unbounded Knapsack Combination Dynamic Programming:

DP Array: Create array dp of size amount + 1 filled with 0. Set dp[0] = 1 (1 way to make amount 0).
Outer Coin Loop: Iterate coin in coins FIRST:
- Iterate $i$ from coin to amount:
- dp[i] += dp[i - coin].
Result: dp[amount] holds the total distinct combination count.

Why Outer Coin Loop Matters

Looping coin in the outer loop ensures coin ordering does not duplicate combinations (e.g., 1+2 and 2+1 count as 1 valid combination). Runs in $O(\text{amount} \times \text{coins.length})$ time and $O(\text{amount})$ space.

Example Walkthrough

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

Target amount 5.

Combinations: 5=5, 5=2+2+1, 5=2+1+1+1, 5=1+1+1+1+1

4 distinct combinations.

Output: 4

Total combination count.

Answer: Coin Change 2 combinations DP

function change(amount, coins) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] += dp[i - coin];
    }
  }
  return dp[amount];
}

💡 Compute combination totals by iterating coins in the outer loop.

Key Takeaways

Outer coin loop counts unique combinations.
Outer amount loop would count permutations instead of combinations.
Runs in $O(A \cdot N)$ time and $O(A)$ space.