Coin Change II

Examples

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

5=5; 2+2+1; 2+1+1+1; 1+1+1+1+1.

Input: amount = 3, coins = [2]
Output: 0

No combination of 2s can ever total an odd number like 3.

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

Constraints

• 1 <= coins.length <= 300

• 1 <= coins[i] <= 5000

• All coin values are distinct

• 0 <= amount <= 5000

Approach

Because the order coins are used in doesn't matter, the trick is to loop over the coin types as one dimension of the table and the amount as the other. Cell (i, a) means: "using only the first i coin types, how many combinations make exactly amount a?"

For each cell, you have two disjoint choices: don't use the i-th coin type at all (carry forward the count from one fewer coin type), or use at least one of it (which reduces the amount by that coin's value, but — since coins are reusable — you're still allowed to use that same coin type again, so you look back at the same row, smaller amount). Add those two counts together.

Processing coin types as the outer loop, rather than amounts, is what guarantees each combination is only counted once — in the order its coin types happen to appear in the list.

Solutions

Brute Force — Recursion

For each coin type in turn, recursively branch on 'skip this coin type entirely' versus 'use one more of this coin type' (staying on the same type, since coins can repeat). A remaining amount of exactly 0 is one valid combination.

function change(amount, coins) {
  function countWays(i, remaining) {
    if (remaining === 0) return 1;
    if (remaining < 0 || i === coins.length) return 0;

    const skipCoin = countWays(i + 1, remaining);
    const useCoin = countWays(i, remaining - coins[i]);
    return skipCoin + useCoin;
  }

  return countWays(0, amount);
}

Time: O(2^amount) in the worst case · Space: O(amount) — recursion depth

Optimal — Bottom-Up 2D Table

Build a table with one row per coin type (plus a row for 'no coins used yet') and one column per amount from 0 to the target. Each cell adds together the 'skip this coin' count and the 'use this coin' count.

function change(amount, coins) {
  const n = coins.length;
  const table = Array.from({ length: n + 1 }, () => new Array(amount + 1).fill(0));

  for (let i = 0; i <= n; i++) {
    table[i][0] = 1; // exactly one way to make amount 0: use no coins
  }

  for (let i = 1; i <= n; i++) {
    for (let a = 1; a <= amount; a++) {
      table[i][a] = table[i - 1][a]; // don't use this coin type at all
      if (a - coins[i - 1] >= 0) {
        table[i][a] += table[i][a - coins[i - 1]]; // use at least one of this coin type
      }
    }
  }

  return table[n][amount];
}

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