Coin Change

Examples

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

11 = 5 + 5 + 1, using 3 coins.

Input: coins = [2], amount = 3
Output: -1

You can only ever make even amounts with 2-value coins.

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

Zero coins are needed to make an amount of 0.

Constraints

• 1 <= coins.length <= 12

• 1 <= coins[i] <= 2^31 - 1

• 0 <= amount <= 10^4

Approach

Think about the last coin used in an optimal solution for amount a. Whatever that coin's value c is, the rest of the solution is just an optimal solution for the smaller amount a - c. Since you don't know in advance which coin was used last, try all of them and take whichever choice leads to the fewest total coins.

That gives the recurrence fewest(a) = 1 + min(fewest(a - c)) over every coin c that fits within a, with fewest(0) = 0 as the base case. Computing this bottom-up — from amount 0 up to the target — means every smaller amount is already solved by the time you need it, avoiding the repeated work that plain recursion would do.

Solutions

Brute Force — Plain Recursion

For each amount, try every coin as the last one used and recurse on the remainder, keeping the option that uses the fewest coins. Correct, but the same amounts get recomputed many times over.

function coinChange(coins, amount) {
  function fewest(remaining) {
    if (remaining === 0) return 0;
    if (remaining < 0) return Infinity;

    let best = Infinity;
    for (const coin of coins) {
      const result = fewest(remaining - coin);
      if (result + 1 < best) best = result + 1;
    }
    return best;
  }

  const answer = fewest(amount);
  return answer === Infinity ? -1 : answer;
}

Time: O(coins.length ^ amount) · Space: O(amount) — recursion depth

Optimal — Bottom-Up Tabulation

Compute the fewest coins needed for every amount from 0 up to the target, reusing the already-solved smaller amounts instead of recursing.

function coinChange(coins, amount) {
  // dp[a] = fewest coins to make amount a; amount+1 stands in for "impossible"
  const dp = new Array(amount + 1).fill(amount + 1);
  dp[0] = 0;

  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a) {
        dp[a] = Math.min(dp[a], dp[a - coin] + 1);
      }
    }
  }

  return dp[amount] > amount ? -1 : dp[amount];
}

Time: O(amount * coins.length) · Space: O(amount)