Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumknapsack-subset-dp

Coin Change II

Problem (restated)

Number of combinations that make up amount with given coin denominations (order does not matter).

Intuition

Outer loop coins, inner amount ascending → combinations not permutations.

Approaches

Unbounded knapsack count

Tested only

Time O(amount · n)Space O(amount)

Idea. dp[0]=1; for coin: for a=coin..amount: dp[a]+=dp[a-coin].

Walkthrough. amount=5, coins=[1,2,5] → 4.

Trade-offs. Swap loop order → permutations (wrong for this problem).

Solution

export function change(amount: number, coins: number[]): number {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const c of coins) {
    for (let a = c; a <= amount; a++) dp[a]! += dp[a - c]!;
  }
  return dp[amount]!;
}

export function change(amount: number, coins: number[]): number {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const c of coins) {
    for (let a = c; a <= amount; a++) dp[a]! += dp[a - c]!;
  }
  return dp[amount]!;
}

Template connection

Knapsack unbounded combinations.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?