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

Unverified

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

For combinations, the coin is the outer loop and the amount is the inner loop. Swapping them counts permutations, so 1 + 2 and 2 + 1 both enter.
dp[0] = 1. Amount 0 answers 1. There is no coin of 0.
Order does not matter. The same coin may be used more than once while filling one amount.