Coin change (fewest coins)

Medium TimeExponential naive (shown); O(amount × coins) memoised SpaceO(amount) stack

Coins come in the denominations coins, each in unlimited supply. Return the fewest coins that make amount exactly. The amount is a whole number, zero or more, and an amount of 0 needs no coins at all. An amount that no combination can make comes back as Infinity.

Examples

Example 1

Input
coins = [1, 3, 4]amount = 6
Output
2
3 + 3 = 6 in two coins; taking the largest first gives 4 + 1 + 1, which is three.

Example 2

Input
coins = [3]amount = 5
Output
Infinity
Threes make 3, 6, 9 and so on, so 5 is unreachable and no count comes back.

The Code

function coinChange(coins, amount) {
  if (amount === 0) return 0;
  if (amount < 0) return Infinity;
  let best = Infinity;
  for (const coin of coins) {
    best = Math.min(best, coinChange(coins, amount - coin) + 1);
  }
  return best;
}
coinChange([1, 3, 4], 6);
Done

The first 34 calls, of 106. This one does not fit on a page.

Step through coinChange([1, 3, 4], 6) call by call

More like this

All dynamic programming examples (20) →