MediumDynamic programming

Coin Change

Q: Can a local fun call itself recursively?

Yes. A local fun declared inside coinChange is in scope in its own body, so it can recurse, and it captures coins and memo from the enclosing function. A lambda stored in a val cannot refer to itself, which is why the solutions use a local fun instead.

Q: Why does 1..amount work when the amount is 0?

1..0 is an empty range in Kotlin, so the loop body never runs and best[0] (0) is returned. Ranges only count upward; a downward walk needs downTo.

Q: Can I use Int.MAX_VALUE as the "unreachable" value?

Only with a guard. Int arithmetic wraps silently, so Int.MAX_VALUE + 1 becomes Int.MIN_VALUE, which wins every minOf. Coins intArrayOf(4, 6) with amount 9 would then return a large negative number instead of -1. Check best[a - c] != Int.MAX_VALUE before adding, or use amount + 1, which has room to grow.

You get an array of distinct positive integers coins, the coin values on offer, and an integer amount. There is an unlimited supply of every value. Return the fewest coins whose values add up to exactly amount.

If no combination of the coins reaches the amount, return -1. An amount of 0 needs no coins, so the answer is 0. Don't trust the shortcut of always taking the largest coin that still fits: for some coin sets it spends more coins than needed, and the first example is one of them.

Examples

Input

coins = [1, 5, 6, 9]
amount = 11

Output2Why5 + 6 pays 11 with two coins. Taking the largest coin first gives 9 + 1 + 1, three coins.

Input

coins = [4, 6]
amount = 9

Output-1WhyEvery total made from 4s and 6s is even, so the odd amount 9 is out of reach.

Constraints

Size: 1 ≤ coins.length ≤ 10
Values: 1 ≤ coins[i] ≤ 50
Amount: 0 ≤ amount ≤ 50
Supply: Coin values are distinct, and each can be used any number of times.
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

3 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

To pay rest, pick any coin c and pay rest - c with as few coins as possible. Try every coin and keep the smallest result. A remainder of 0 costs nothing, and a negative remainder is a dead end, scored as infinity so min never picks it. It is correct but solves the same remainders over and over: with coins [1, 5, 6, 9] it makes 205 calls for an amount of 11, 72,813 for 27, and about 2.3 × 10⁴⁸ for 300.

from math import inf


def coin_change(coins: list[int], amount: int) -> int:
    def fewest(rest: int) -> float:
        if rest == 0:
            return 0
        if rest < 0:
            return inf
        return 1 + min(fewest(rest - c) for c in coins)

    result = fewest(amount)
    return -1 if result == inf else int(result)

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

The answer for a remainder never changes, so compute it once. Putting @functools.cache on the inner function stores each result the first time it is found. There are only amount + 1 remainders, and each one tries every coin once. The cache is defined inside coin_change, so each call starts fresh with its own coins. The catch is depth: the recursion goes one level deeper per coin taken, so large amounts hit Python's recursion limit (see the FAQ).

from functools import cache
from math import inf


def coin_change(coins: list[int], amount: int) -> int:
    @cache
    def fewest(rest: int) -> float:
        if rest == 0:
            return 0
        if rest < 0:
            return inf
        return 1 + min(fewest(rest - c) for c in coins)

    result = fewest(amount)
    return -1 if result == inf else int(result)

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Turn the cache into a list. best[a] holds the fewest coins that make a, and best[0] is 0. Walk a upward; by the time you reach it, every smaller amount is already final, so best[a - c] + 1 for each coin that fits gives the answer. Amounts that can't be made keep a value one bigger than any real answer, which is cheaper than mixing floats into a list of ints. The work is the same as the cached version, amount × len(coins) steps, but there is no recursion, so no depth limit and no call overhead. The sentinel amount + 1 works because even a coin of 1 never needs more than amount coins.

def coin_change(coins: list[int], amount: int) -> int:
    too_many = amount + 1  # more coins than any real answer can use
    best = [0] + [too_many] * amount  # best[a] = fewest coins that make a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return -1 if best[amount] == too_many else best[amount]

3 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

Think about the first coin you hand over. Whatever it is, the rest of the job is the same problem with a smaller target. So an inner arrow function fewest(rest) loops over the coins, asks for fewest(rest - c), adds one, and keeps the minimum. Hitting exactly 0 costs nothing. Going below 0 returns Infinity, which JavaScript treats as an ordinary number, so Math.min quietly ignores those branches. The trouble is the call count, because the same remainders get recomputed down every branch: with coins [1, 5, 6, 9], 205 calls for an amount of 11 and 72,813 for 27. The growth is exponential in the amount, so a target in the hundreds will never finish.

function coinChange(coins, amount) {
  const fewest = (rest) => {
    if (rest === 0) return 0;
    if (rest < 0) return Infinity; // overshot: this path can never pay exactly
    let best = Infinity;
    for (const c of coins) best = Math.min(best, fewest(rest - c) + 1);
    return best;
  };
  const result = fewest(amount);
  return result === Infinity ? -1 : result;
}

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

A given remainder always has the same answer, so store it the first time it is worked out. The Map is created inside coinChange, which means the closure sees one cache per call and two calls with different coins never share stale results. Only amount + 1 distinct remainders exist, and each loops over the coins once. Unreachable remainders are cached too, stored as Infinity, so a dead end is explored only once. What remains is the call stack: with a 1 among the coins the first path peels off one unit per level, so the depth equals the amount, and V8 runs out of stack long before memory (numbers in the FAQ).

function coinChange(coins, amount) {
  const memo = new Map(); // remainder -> fewest coins, fresh for every call
  const fewest = (rest) => {
    if (rest === 0) return 0;
    if (rest < 0) return Infinity;
    if (memo.has(rest)) return memo.get(rest);
    let best = Infinity;
    for (const c of coins) best = Math.min(best, fewest(rest - c) + 1);
    memo.set(rest, best);
    return best;
  };
  const result = fewest(amount);
  return result === Infinity ? -1 : result;
}

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Replace the memo with an array indexed by amount and fill it from the small end. Start every slot at Infinity except best[0], which is 0. When the outer loop reaches a, every smaller slot already holds its final value, so trying each coin c that is not bigger than a and comparing best[a - c] + 1 settles slot a for good. No function calls, no stack. Infinity + 1 is still Infinity, so an unreachable best[a - c] can never beat a real count, and no made-up sentinel such as amount + 1 is needed. With an amount of 0 the loop body never runs and best[0] is returned as is.

function coinChange(coins, amount) {
  const best = new Array(amount + 1).fill(Infinity); // best[a] = fewest coins that make a
  best[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 1;
    }
  }
  return best[amount] === Infinity ? -1 : best[amount];
}

3 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

Pick the first coin to hand over; what is left is the same question for rest - c. A nested function fewest(rest: number): number tries every coin, adds one to the best sub-answer and keeps the minimum. Exactly 0 is done, below 0 is a dead end that returns Infinity, which is a plain number in TypeScript, so the return type stays simple and Math.min drops those branches by itself. Correct, but the same remainders are solved over and over: coins [1, 5, 6, 9] take 205 calls for 11 and 72,813 for 27, and the count keeps multiplying as the amount grows.

function coinChange(coins: number[], amount: number): number {
  function fewest(rest: number): number {
    if (rest === 0) return 0;
    if (rest < 0) return Infinity; // overshot: no exact payment down this path
    let best = Infinity;
    for (const c of coins) best = Math.min(best, fewest(rest - c) + 1);
    return best;
  }
  const result = fewest(amount);
  return result === Infinity ? -1 : result;
}

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

A remainder always has the same answer, so cache it in a Map<number, number> created inside coinChange, one fresh cache per call. Dead ends are cached too, as Infinity, so each of the amount + 1 remainders is worked out once with one pass over the coins. memo.get is typed number | undefined, and checking the result against undefined both narrows the type and keeps a cached 0. The recursion depth still grows with the amount when a small coin is on offer, so very large amounts hit the engine's stack limit.

function coinChange(coins: number[], amount: number): number {
  const memo = new Map<number, number>(); // remainder -> fewest coins
  function fewest(rest: number): number {
    if (rest === 0) return 0;
    if (rest < 0) return Infinity;
    const cached = memo.get(rest);
    if (cached !== undefined) return cached;
    let best = Infinity;
    for (const c of coins) best = Math.min(best, fewest(rest - c) + 1);
    memo.set(rest, best);
    return best;
  }
  const result = fewest(amount);
  return result === Infinity ? -1 : result;
}

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Fill a number[] from 0 upward instead of recursing. best[0] is 0 and every other slot starts at Infinity. When the loop reaches a, all smaller slots are final, so each coin c <= a offers best[a - c] + 1 and the slot keeps the smallest offer. Infinity + 1 stays Infinity, so an unreachable slot never wins, and the last line maps it to -1. Same amount × coins steps as the memo, with no calls and no stack depth.

function coinChange(coins: number[], amount: number): number {
  const best: number[] = new Array(amount + 1).fill(Infinity); // best[a] = fewest coins that make a
  best[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 1;
    }
  }
  return best[amount] === Infinity ? -1 : best[amount];
}

3 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

Think of the first coin handed over. If it is c, what remains is the cheapest way to pay rest - c, so recurse once per coin and add one to the smallest answer. Exactly 0 left is a finished payment; below 0 is an overshoot. Java's int has no infinity value, so fewest returns -1 to mean "impossible" and the caller filters it out. A local lambda cannot refer to itself, so the helper is a plain static method and coins is passed down on every call. The answers are right; the cost is not, because identical remainders are recomputed on every branch that reaches them. With {1, 5, 6, 9}, amount 11 takes 205 calls, amount 27 takes 72,813, and 300 would take about 2.3 × 10⁴⁸. HotSpot can compile the method to fast machine code, but that only shaves a constant off an exponential.

import java.util.*;

public class Main {
    static int coinChange(int[] coins, int amount) {
        return fewest(coins, amount);
    }

    // -1 means rest cannot be paid
    static int fewest(int[] coins, int rest) {
        if (rest == 0) {
            return 0;
        }
        if (rest < 0) {
            return -1;
        }
        int best = -1;
        for (int c : coins) {
            int sub = fewest(coins, rest - c);
            if (sub >= 0 && (best < 0 || sub + 1 < best)) {
                best = sub + 1;
            }
        }
        return best;
    }
}

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

Each remainder has one fixed answer, so remember it. The cache is a plain int[] memo indexed by remainder, which avoids the boxing a HashMap<Integer, Integer> would add on every lookup. A new int[] is all zeros, and 0 is a legitimate result (so is -1), so Arrays.fill(memo, UNKNOWN) marks every slot with -2 before the search begins. That leaves amount + 1 calls doing real work, each looping over the coins once. A new memo per coinChange call keeps different coin sets apart. Depth is what limits it: each coin taken adds a stack frame, and this site's JVM runs with a 512 KB thread stack (-Xss512k). Coins {1, 5, 6, 9} still return 334 at amount 3,000, but 4,000 ends in StackOverflowError; the FAQ explains why.

import java.util.*;

public class Main {
    static final int UNKNOWN = -2; // -1 already means "cannot be paid"

    static int coinChange(int[] coins, int amount) {
        int[] memo = new int[amount + 1];
        Arrays.fill(memo, UNKNOWN);
        return fewest(coins, amount, memo);
    }

    static int fewest(int[] coins, int rest, int[] memo) {
        if (rest == 0) {
            return 0;
        }
        if (rest < 0) {
            return -1;
        }
        if (memo[rest] != UNKNOWN) {
            return memo[rest];
        }
        int best = -1;
        for (int c : coins) {
            int sub = fewest(coins, rest - c, memo);
            if (sub >= 0 && (best < 0 || sub + 1 < best)) {
                best = sub + 1;
            }
        }
        memo[rest] = best;
        return best;
    }
}

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Now compute the memo in order instead of on demand. best[a] is the answer for amount a; Arrays.fill sets every slot to tooMany (amount + 1), then best[0] = 0 fixes the base case. As a climbs from 1, all entries below it are complete, so each coin c <= a offers best[a - c] + 1 and the entry keeps the lowest offer. An unreachable entry stays at tooMany, larger than any genuine count, so it never wins a comparison, and one ternary at the end maps it to -1. The step count matches the memo, amount * coins.length, but nothing recurses, so -Xss no longer matters and no method call is paid per step. amount + 1 is big enough because a real answer never uses more coins than the amount, and small enough that best[a - c] + 1 cannot wrap past Integer.MAX_VALUE (see the FAQ).

import java.util.*;

public class Main {
    static int coinChange(int[] coins, int amount) {
        int tooMany = amount + 1; // more coins than any real answer can use
        int[] best = new int[amount + 1]; // best[a] = fewest coins that make a
        Arrays.fill(best, tooMany);
        best[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a && best[a - c] + 1 < best[a]) {
                    best[a] = best[a - c] + 1;
                }
            }
        }
        return best[amount] == tooMany ? -1 : best[amount];
    }
}

3 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

Paying rest means choosing one coin c to hand over first, then paying rest - c as cheaply as possible; the answer is the best of those choices plus one. Landing on exactly 0 means nothing is left to pay, and dropping below 0 means that choice failed. Go's int has no infinity, so -1 stands for "impossible" and the loop ignores it. Declaring var fewest func(rest int) int on its own line before assigning the function literal is what lets the closure call itself while it reads coins from the enclosing function. The trouble is repetition: a remainder gets re-solved along every path that reaches it. For coins [1 5 6 9], an amount of 11 already costs 205 calls, 27 costs 72,813, and 300 would need roughly 2.3 × 10⁴⁸. Native machine code does not rescue an exponential call count.

package main

func coinChange(coins []int, amount int) int {
	var fewest func(rest int) int // -1 means rest cannot be paid
	fewest = func(rest int) int {
		if rest == 0 {
			return 0
		}
		if rest < 0 {
			return -1
		}
		best := -1
		for _, c := range coins {
			if sub := fewest(rest - c); sub >= 0 && (best < 0 || sub+1 < best) {
				best = sub + 1
			}
		}
		return best
	}
	return fewest(amount)
}

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

Since fewest(rest) always returns the same thing for the same rest, store it. Go has no decorator for this, so the closure carries its own table: memo := make([]int, amount+1), indexed by remainder. A fresh slice is all zeros, but 0 is a real answer, and so is -1; that is why a loop first sets every slot to the unknown constant, -2. With amount + 1 possible remainders, each looping over the coins once, the work drops to O(n·k). Because memo is made per call of coinChange, results for one coin set never leak into another. Deep recursion is less of a worry in Go than elsewhere: there is no fixed frame limit, and the runtime enlarges the goroutine stack as the chain lengthens, about one frame per coin taken (the FAQ has numbers). You still pay for those frames in memory and for a function call at every step.

package main

func coinChange(coins []int, amount int) int {
	const unknown = -2 // -1 already means "cannot be paid"
	memo := make([]int, amount+1)
	for i := range memo {
		memo[i] = unknown
	}
	var fewest func(rest int) int
	fewest = func(rest int) int {
		if rest == 0 {
			return 0
		}
		if rest < 0 {
			return -1
		}
		if memo[rest] != unknown {
			return memo[rest]
		}
		best := -1
		for _, c := range coins {
			if sub := fewest(rest - c); sub >= 0 && (best < 0 || sub+1 < best) {
				best = sub + 1
			}
		}
		memo[rest] = best
		return best
	}
	return fewest(amount)
}

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Flip the recursion around. Let best[a] be the answer for amount a; make already zeroes the slice, so best[0] = 0 needs no line of code. Loop a from 1 to amount: every smaller entry is settled by then, so trying each coin no bigger than a and keeping the lowest best[a-c] + 1 completes the entry. Unreachable amounts hold tooMany, which is amount + 1 and loses every < test against a real count, so the inner loop has no -1 branch. Go has no ternary operator, so mapping that sentinel back to -1 at the end is an ordinary if. It does amount * len(coins) steps like the memo, but as nested for loops over a single slice, so the stack never grows and no function is called per step.

package main

func coinChange(coins []int, amount int) int {
	tooMany := amount + 1 // more coins than any real answer can use
	best := make([]int, amount+1)
	for a := 1; a <= amount; a++ {
		best[a] = tooMany // best[a] = fewest coins that make a
		for _, c := range coins {
			if c <= a && best[a-c]+1 < best[a] {
				best[a] = best[a-c] + 1
			}
		}
	}
	if best[amount] == tooMany {
		return -1
	}
	return best[amount]
}

3 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

Whichever coin c goes first, the rest of the payment is the same question for rest - c, so Fewest asks it once per coin and adds one to the smallest answer. A remainder of exactly 0 is a finished payment; below 0 is an overshoot. C#'s int has no infinity, so the helper returns -1 for "cannot be paid" and the loop skips those results. A lambda cannot call itself before it is assigned, so the helper is a second static method on Solution and coins travels down as a parameter. The answers are right; the running time is not, because every branch that lands on the same remainder solves it again. With { 1, 5, 6, 9 } amount 11 costs 205 calls, amount 27 costs 72,813, and amount 300 would cost about 2.3 × 10⁴⁸; RyuJIT makes each call cheap, but it cannot make an exponential count small.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int CoinChange(int[] coins, int amount)
    {
        return Fewest(coins, amount);
    }

    // -1 means rest cannot be paid
    static int Fewest(int[] coins, int rest)
    {
        if (rest == 0) return 0;
        if (rest < 0) return -1;
        int best = -1;
        foreach (int c in coins)
        {
            int sub = Fewest(coins, rest - c);
            if (sub >= 0 && (best < 0 || sub + 1 < best)) best = sub + 1;
        }
        return best;
    }
}

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

A remainder has exactly one answer, so store it the first time it is found. The cache is an int[] memo indexed by remainder: a plain index instead of the hashing a Dictionary<int, int> would do on every lookup. A fresh array is all zeros, and both 0 and -1 are real results, so Array.Fill(memo, Unknown) stamps every slot with -2 before the search starts. Only amount + 1 calls then do real work, each trying every coin once. The array is created inside CoinChange, so a second call with other coins never sees stale answers. What limits this version is depth, not time: each coin taken is one more frame, and the first path explored keeps taking the smallest coin, so a large amount with a coin of 1 can exhaust the thread's stack. In .NET that is a StackOverflowException that ends the process; the FAQ has the details.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    const int Unknown = -2; // -1 already means "cannot be paid"

    public static int CoinChange(int[] coins, int amount)
    {
        var memo = new int[amount + 1];
        Array.Fill(memo, Unknown);
        return Fewest(coins, amount, memo);
    }

    static int Fewest(int[] coins, int rest, int[] memo)
    {
        if (rest == 0) return 0;
        if (rest < 0) return -1;
        if (memo[rest] != Unknown) return memo[rest];
        int best = -1;
        foreach (int c in coins)
        {
            int sub = Fewest(coins, rest - c, memo);
            if (sub >= 0 && (best < 0 || sub + 1 < best)) best = sub + 1;
        }
        memo[rest] = best;
        return best;
    }
}

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Fill the memo in order instead of on demand. best[a] is the answer for amount a; Array.Fill sets every slot to tooMany (amount + 1) and best[0] = 0 plants the base case. As a climbs from 1, every entry below it is already final, so each coin c <= a offers best[a - c] + 1 and the slot keeps the lowest offer. An amount nothing can reach stays at tooMany, which is larger than any genuine count and therefore never wins a comparison; one conditional at the end turns it into -1. The step count equals the memo's, amount * coins.Length, but nothing recurses, so the stack size is irrelevant and no call is paid per step. amount + 1 is big enough because no real answer uses more coins than the amount, and small enough that best[a - c] + 1 stays far from int.MaxValue.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int CoinChange(int[] coins, int amount)
    {
        int tooMany = amount + 1; // more coins than any real answer can use
        var best = new int[amount + 1]; // best[a] = fewest coins that make a
        Array.Fill(best, tooMany);
        best[0] = 0;
        for (int a = 1; a <= amount; a++)
        {
            foreach (int c in coins)
            {
                if (c <= a && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 1;
            }
        }
        return best[amount] == tooMany ? -1 : best[amount];
    }
}

3 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

Whatever coin c goes first, the rest is the same problem for rest - c. A private member fewest tries every coin and keeps the smallest sub-answer plus one. int has no infinity, so -1 stands for "cannot be paid" and the loop skips it. coins is passed as a const vector<int>&, so no call copies it. The answers are right, but identical remainders are recomputed on every branch: coins [1, 5, 6, 9] take 205 calls for 11 and 72,813 for 27, and compiled code only makes each call cheaper, not fewer.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        return fewest(coins, amount);
    }

private:
    // -1 means rest cannot be paid
    int fewest(const vector<int>& coins, int rest) {
        if (rest == 0) return 0;
        if (rest < 0) return -1;
        int best = -1;
        for (int c : coins) {
            int sub = fewest(coins, rest - c);
            if (sub >= 0 && (best < 0 || sub + 1 < best)) best = sub + 1;
        }
        return best;
    }
};

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

Each remainder has one fixed answer, so remember it in a vector<int> memo of size amount + 1, built per call and passed down by reference. Both 0 and -1 are real results, so the vector starts filled with -2 for "not computed". Each remainder then does its loop over the coins once, amount × coins steps in all. A vector indexed by remainder beats an unordered_map here: no hashing and one contiguous block. The recursion depth still follows the amount when a 1 is on offer, so a huge amount can overflow the stack, which in C++ is a crash, not an exception you can catch.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> memo(amount + 1, UNKNOWN);
        return fewest(coins, amount, memo);
    }

private:
    static constexpr int UNKNOWN = -2; // -1 already means "cannot be paid"

    int fewest(const vector<int>& coins, int rest, vector<int>& memo) {
        if (rest == 0) return 0;
        if (rest < 0) return -1;
        if (memo[rest] != UNKNOWN) return memo[rest];
        int best = -1;
        for (int c : coins) {
            int sub = fewest(coins, rest - c, memo);
            if (sub >= 0 && (best < 0 || sub + 1 < best)) best = sub + 1;
        }
        memo[rest] = best;
        return best;
    }
};

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Compute the table in order instead. vector<int> best(amount + 1, amount + 1) starts every slot at a value no real answer reaches (an answer never uses more coins than the amount), then best[0] = 0. As a climbs, all smaller slots are final, so each coin c <= a offers best[a - c] + 1 and min keeps the lowest. A slot still above amount at the end was unreachable and becomes -1. Same step count as the memo, no recursion, and the sentinel leaves room for the + 1 without overflow.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> best(amount + 1, amount + 1); // best[a] = fewest coins that make a
        best[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a) best[a] = min(best[a], best[a - c] + 1);
            }
        }
        return best[amount] > amount ? -1 : best[amount];
    }
};

3 reference approaches in C, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

Whatever coin goes first, what is left is the same problem for rest - c. A static helper takes the pointer and the size along with the remainder, tries every coin and keeps the smallest sub-answer plus one, with -1 meaning "cannot be paid" since C has no integer infinity. Nothing is allocated, so there is nothing to free. The cost is the repetition: coins [1, 5, 6, 9] take 205 calls for 11 and 72,813 for 27, growing exponentially with the amount.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

// -1 means rest cannot be paid
static int fewest(const int* coins, int coinsSize, int rest) {
    if (rest == 0) return 0;
    if (rest < 0) return -1;
    int best = -1;
    for (int i = 0; i < coinsSize; i++) {
        int sub = fewest(coins, coinsSize, rest - coins[i]);
        if (sub >= 0 && (best < 0 || sub + 1 < best)) best = sub + 1;
    }
    return best;
}

int coinChange(int* coins, int coinsSize, int amount) {
    return fewest(coins, coinsSize, amount);
}

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

Cache each remainder's answer in an int array of amount + 1 slots from malloc. 0 and -1 are both real answers, so a loop sets every slot to -2 first (memset only writes bytes, so it cannot store -2). Each remainder then loops over the coins once. The result is copied out before free(memo), so the function leaks nothing. Depth still follows the amount when a 1 is on offer, and a stack overflow in C is a crash.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

#define UNKNOWN (-2) // -1 already means "cannot be paid"

static int fewest(const int* coins, int coinsSize, int rest, int* memo) {
    if (rest == 0) return 0;
    if (rest < 0) return -1;
    if (memo[rest] != UNKNOWN) return memo[rest];
    int best = -1;
    for (int i = 0; i < coinsSize; i++) {
        int sub = fewest(coins, coinsSize, rest - coins[i], memo);
        if (sub >= 0 && (best < 0 || sub + 1 < best)) best = sub + 1;
    }
    memo[rest] = best;
    return best;
}

int coinChange(int* coins, int coinsSize, int amount) {
    int* memo = malloc((amount + 1) * sizeof *memo);
    for (int a = 0; a <= amount; a++) memo[a] = UNKNOWN;
    int result = fewest(coins, coinsSize, amount, memo);
    free(memo);
    return result;
}

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Fill a malloc'ed table from 0 upward. Every slot starts at amount + 1, more coins than any real answer uses, and best[0] = 0. When a is reached, all smaller slots are final, so each coin c <= a offers best[a - c] + 1 and the slot keeps the lowest. A slot still above amount was unreachable and becomes -1. The answer is read into a local before free(best); no recursion, so no depth limit.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

int coinChange(int* coins, int coinsSize, int amount) {
    int* best = malloc((amount + 1) * sizeof *best); // best[a] = fewest coins that make a
    for (int a = 0; a <= amount; a++) best[a] = amount + 1;
    best[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int i = 0; i < coinsSize; i++) {
            int c = coins[i];
            if (c <= a && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 1;
        }
    }
    int result = best[amount] > amount ? -1 : best[amount];
    free(best);
    return result;
}

3 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

Whatever coin c goes first, the rest is the same problem for rest - c. A local fun fewest inside coinChange captures coins and returns Int?, with null for a remainder that cannot be paid. coins.map { fewest(rest - it) } scores every coin, filterNotNull() drops the dead ends (IntArray has no mapNotNull),minOrNull() picks the best, and ?.plus(1) counts the coin just taken. It is correct but recomputes the same remainders on every branch: 205 calls for coins [1, 5, 6, 9] and amount 11, 72,813 for 27.

class Solution {
    fun coinChange(coins: IntArray, amount: Int): Int {
        // null means rest cannot be paid
        fun fewest(rest: Int): Int? {
            if (rest == 0) return 0
            if (rest < 0) return null
            return coins.map { fewest(rest - it) }.filterNotNull().minOrNull()?.plus(1)
        }
        return fewest(amount) ?: -1
    }
}

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

Each remainder has one fixed answer, so store it in an IntArray indexed by remainder, which keeps the values unboxed. IntArray(amount + 1) { UNKNOWN } fills every slot with -2, because both 0 and -1 (cannot be paid) are real results. The local fun captures the array, so only amount + 1 calls do real work, each looping over the coins once. Every Kotlin call is a JVM stack frame, so very large amounts end in StackOverflowError (see the FAQ).

private const val UNKNOWN = -2 // -1 already means "cannot be paid"

class Solution {
    fun coinChange(coins: IntArray, amount: Int): Int {
        val memo = IntArray(amount + 1) { UNKNOWN }

        fun fewest(rest: Int): Int {
            if (rest == 0) return 0
            if (rest < 0) return -1
            if (memo[rest] != UNKNOWN) return memo[rest]
            var best = -1
            for (c in coins) {
                val sub = fewest(rest - c)
                if (sub >= 0 && (best < 0 || sub + 1 < best)) best = sub + 1
            }
            memo[rest] = best
            return best
        }

        return fewest(amount)
    }
}

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Fill the memo in order instead. best[a] is the fewest coins that make a; the IntArray initialiser puts 0 in slot 0 and tooMany (amount + 1) everywhere else. Walking a through 1..amount, every smaller entry is final, so each coin that fits offers best[a - c] + 1 and minOf keeps the lowest. An entry still at tooMany was never reached and becomes -1. Same amount × coins.size steps as the memo, with no recursion and no stack limit.

class Solution {
    fun coinChange(coins: IntArray, amount: Int): Int {
        val tooMany = amount + 1 // more coins than any real answer can use
        val best = IntArray(amount + 1) { if (it == 0) 0 else tooMany }
        for (a in 1..amount) {
            for (c in coins) {
                if (c <= a) best[a] = minOf(best[a], best[a - c] + 1)
            }
        }
        return if (best[amount] == tooMany) -1 else best[amount]
    }
}

3 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

Whatever coin c goes first, the rest is the same problem for rest - c. A nested fn fewest takes the coins as a &[i32] slice and returns Option<i32>, with None for a remainder that cannot be paid. The iterator chain filter_map drops the dead ends, min() picks the best and map(|n| n + 1) counts the coin just taken; unwrap_or(-1) turns None into the required -1. Correct, but the same remainders are solved again on every branch: 205 calls for coins [1, 5, 6, 9] and amount 11, 72,813 for 27.

impl Solution {
    pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
        // None means rest cannot be paid
        fn fewest(coins: &[i32], rest: i32) -> Option<i32> {
            if rest == 0 {
                return Some(0);
            }
            if rest < 0 {
                return None;
            }
            coins.iter().filter_map(|&c| fewest(coins, rest - c)).min().map(|n| n + 1)
        }
        fewest(&coins, amount).unwrap_or(-1)
    }
}

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

Each remainder has one fixed answer, so cache it in a Vec indexed by remainder (cast to usize). The slot type is Option<Option<i32>>: the outer None means not computed yet, Some(None) means cannot be paid. The helper is an associated function that takes the memo as &mut [_], so the borrow checker sees one mutable owner through the whole recursion. Only amount + 1 calls do real work, each looping over the coins once.

impl Solution {
    pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
        // memo[rest]: None = not computed yet, Some(None) = cannot be paid
        let mut memo: Vec<Option<Option<i32>>> = vec![None; amount as usize + 1];
        Self::fewest(&coins, amount, &mut memo).unwrap_or(-1)
    }

    fn fewest(coins: &[i32], rest: i32, memo: &mut [Option<Option<i32>>]) -> Option<i32> {
        if rest == 0 {
            return Some(0);
        }
        if rest < 0 {
            return None;
        }
        if let Some(known) = memo[rest as usize] {
            return known;
        }
        let mut best: Option<i32> = None;
        for &c in coins {
            if let Some(sub) = Self::fewest(coins, rest - c, memo) {
                best = Some(best.map_or(sub + 1, |b| b.min(sub + 1)));
            }
        }
        memo[rest as usize] = Some(best);
        best
    }
}

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Fill the memo in order instead. best[a] is the fewest coins that make a: vec![too_many; n + 1] starts every slot one above any real answer and best[0] = 0 sets the base case. Walking a through 1..=n, every smaller entry is final, so each coin that fits offers best[a - c] + 1. Comparing c <= a before subtracting matters: a - c on usize would otherwise underflow and panic in this debug build. No recursion, no stack depth.

impl Solution {
    pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
        let n = amount as usize;
        let too_many = amount + 1; // more coins than any real answer can use
        let mut best = vec![too_many; n + 1]; // best[a] = fewest coins that make a
        best[0] = 0;
        for a in 1..=n {
            for &c in &coins {
                let c = c as usize;
                if c <= a && best[a - c] + 1 < best[a] {
                    best[a] = best[a - c] + 1;
                }
            }
        }
        if best[n] == too_many { -1 } else { best[n] }
    }
}

3 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

Whatever coin c goes first, the rest is the same problem for rest - c. A nested func fewest captures coins and returns Int?, with nil for a remainder that cannot be paid. if let skips the dead ends and min(best ?? Int.max, sub + 1) keeps the lowest count; ?? -1 at the top turns nil into the required -1. Correct, but the same remainders are solved again on every branch: 205 calls for coins [1, 5, 6, 9] and amount 11, 72,813 for 27.

class Solution {
    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        // nil means rest cannot be paid
        func fewest(_ rest: Int) -> Int? {
            if rest == 0 { return 0 }
            if rest < 0 { return nil }
            var best: Int?
            for c in coins {
                if let sub = fewest(rest - c) {
                    best = min(best ?? Int.max, sub + 1)
                }
            }
            return best
        }
        return fewest(amount) ?? -1
    }
}

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

Each remainder has one fixed answer, so cache it in a [Int: Int?] dictionary. The subscript returns Int??: the outer optional says whether the key is there, the inner one is the answer, so if let known = memo[rest] also returns a cached nil. Storing it needs memo[rest] = .some(best), because assigning a bare nil would delete the key. The nested function captures memo by reference, so only amount + 1 calls do real work.

class Solution {
    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        // memo[rest] holds nil when rest cannot be paid
        var memo: [Int: Int?] = [:]

        func fewest(_ rest: Int) -> Int? {
            if rest == 0 { return 0 }
            if rest < 0 { return nil }
            if let known = memo[rest] { return known }
            var best: Int?
            for c in coins {
                if let sub = fewest(rest - c) {
                    best = min(best ?? Int.max, sub + 1)
                }
            }
            memo[rest] = .some(best)
            return best
        }

        return fewest(amount) ?? -1
    }
}

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Fill the memo in order instead. best[a] is the fewest coins that make a: [Int](repeating: tooMany, count: amount + 1) starts every slot one above any real answer and best[0] = 0 sets the base case. The outer loop is 1..<best.count, which is empty for an amount of 0 (a closed 1...0 would trap). A where c <= a clause skips coins that do not fit, and each of the others offers best[a - c] + 1. No recursion and no dictionary hashing.

class Solution {
    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        let tooMany = amount + 1 // more coins than any real answer can use
        var best = [Int](repeating: tooMany, count: amount + 1) // best[a] = fewest coins that make a
        best[0] = 0
        for a in 1..<best.count {
            for c in coins where c <= a {
                best[a] = min(best[a], best[a - c] + 1)
            }
        }
        return best[amount] == tooMany ? -1 : best[amount]
    }
}

3 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

Whatever coin $c goes first, the rest is the same problem for $rest - $c. A private method fewest tries every coin and returns the smallest count plus one, with -1 meaning the remainder cannot be paid. Passing $coins down on every call is cheap, because PHP arrays are copy-on-write and nothing writes to them. Correct, but the same remainders are solved again on every branch: 205 calls for coins [1, 5, 6, 9] and amount 11, 72,813 for 27.

<?php
class Solution {
    /**
     * @param int[] $coins
     * @param int $amount
     * @return int
     */
    function coinChange(array $coins, int $amount): int {
        return $this->fewest($coins, $amount);
    }

    // -1 means $rest cannot be paid
    private function fewest(array $coins, int $rest): int {
        if ($rest === 0) {
            return 0;
        }
        if ($rest < 0) {
            return -1;
        }
        $best = -1;
        foreach ($coins as $c) {
            $sub = $this->fewest($coins, $rest - $c);
            if ($sub >= 0 && ($best < 0 || $sub + 1 < $best)) {
                $best = $sub + 1;
            }
        }
        return $best;
    }
}

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

Each remainder has one fixed answer, so cache it in an array property $memo keyed by remainder, reset at the start of every coinChange call so different coin sets never share results. isset($this->memo[$rest]) is a constant-time check, and because the impossible answer is stored as the integer -1 rather than null, isset still sees it. Only amount + 1 calls do real work.

<?php
class Solution {
    private array $memo = [];
    private array $coins = [];

    /**
     * @param int[] $coins
     * @param int $amount
     * @return int
     */
    function coinChange(array $coins, int $amount): int {
        $this->coins = $coins;
        $this->memo = [];
        return $this->fewest($amount);
    }

    // -1 means $rest cannot be paid
    private function fewest(int $rest): int {
        if ($rest === 0) {
            return 0;
        }
        if ($rest < 0) {
            return -1;
        }
        if (isset($this->memo[$rest])) {
            return $this->memo[$rest];
        }
        $best = -1;
        foreach ($this->coins as $c) {
            $sub = $this->fewest($rest - $c);
            if ($sub >= 0 && ($best < 0 || $sub + 1 < $best)) {
                $best = $sub + 1;
            }
        }
        return $this->memo[$rest] = $best;
    }
}

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Fill the memo in order instead. $best[$a] is the fewest coins that make $a: array_fill(0, $amount + 1, $tooMany) starts every slot one above any real answer and $best[0] = 0 sets the base case. Walking $a upward, every smaller entry is final, so each coin that fits offers $best[$a - $c] + 1 and min keeps the lowest. No recursion and no method call per step, which matters in an interpreter.

<?php
class Solution {
    /**
     * @param int[] $coins
     * @param int $amount
     * @return int
     */
    function coinChange(array $coins, int $amount): int {
        $tooMany = $amount + 1; // more coins than any real answer can use
        $best = array_fill(0, $amount + 1, $tooMany); // $best[$a] = fewest coins that make $a
        $best[0] = 0;
        for ($a = 1; $a <= $amount; $a++) {
            foreach ($coins as $c) {
                if ($c <= $a) {
                    $best[$a] = min($best[$a], $best[$a - $c] + 1);
                }
            }
        }
        return $best[$amount] === $tooMany ? -1 : $best[$amount];
    }
}

3 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

Whatever coin c goes first, the rest is the same problem for rest - c. The helper fewest returns nil for a remainder that cannot be paid, so coins.filter_map drops the dead ends in one pass and min picks the best (it is nil on an empty array). best && best + 1 counts the coin just taken, and || -1 turns nil into the required -1. Correct, but the same remainders are solved again on every branch: 205 calls for coins [1, 5, 6, 9] and amount 11, 72,813 for 27.

# @param {Integer[]} coins
# @param {Integer} amount
# @return {Integer}
def coin_change(coins, amount)
  fewest(coins, amount) || -1
end

# nil means rest cannot be paid
def fewest(coins, rest)
  return 0 if rest.zero?
  return nil if rest.negative?

  best = coins.filter_map { |c| fewest(coins, rest - c) }.min
  best && best + 1
end

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

Each remainder has one fixed answer, and a Hash with a default block computes it exactly once: Hash.new { |h, rest| h[rest] = … } runs the block only for a missing key and stores what it returns. Inside the block, h[rest - c] recurses through the same hash. A stored nil (cannot be paid) still counts as present, so the block never runs twice for one key. The hash is local to the call, so different coin sets never share results.

# @param {Integer[]} coins
# @param {Integer} amount
# @return {Integer}
def coin_change(coins, amount)
  # fewest[rest] = fewest coins that make rest, or nil when it cannot be paid
  fewest = Hash.new do |h, rest|
    h[rest] =
      if rest.zero?
        0
      elsif rest.negative?
        nil
      else
        best = coins.filter_map { |c| h[rest - c] }.min
        best && best + 1
      end
  end
  fewest[amount] || -1
end

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Fill the memo in order instead. best[a] is the fewest coins that make a: Array.new(amount + 1, too_many) starts every slot one above any real answer and best[0] = 0 sets the base case. Walking (1..amount), every smaller entry is final, so each coin that fits offers best[a - c] + 1. The c <= a guard is essential in Ruby: a negative index does not raise, it reads from the end of the array. No recursion and no block per remainder.

# @param {Integer[]} coins
# @param {Integer} amount
# @return {Integer}
def coin_change(coins, amount)
  too_many = amount + 1 # more coins than any real answer can use
  best = Array.new(amount + 1, too_many) # best[a] = fewest coins that make a
  best[0] = 0
  (1..amount).each do |a|
    coins.each do |c|
      next if c > a

      best[a] = best[a - c] + 1 if best[a - c] + 1 < best[a]
    end
  end
  best[amount] == too_many ? -1 : best[amount]
end

3 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

Whatever coin c goes first, the rest is the same problem for rest - c. A local function int? fewest(int rest) captures coins and returns null for a remainder that cannot be paid. A null check skips the dead ends and keeps the lowest count in a nullable best, which Dart promotes to int after the check; ?? -1 at the top turns null into the required -1. Correct, but the same remainders are solved again on every branch: 205 calls for coins [1, 5, 6, 9] and amount 11, 72,813 for 27.

class Solution {
  int coinChange(List<int> coins, int amount) {
    // null means rest cannot be paid
    int? fewest(int rest) {
      if (rest == 0) return 0;
      if (rest < 0) return null;
      int? best;
      for (final c in coins) {
        final sub = fewest(rest - c);
        if (sub != null && (best == null || sub + 1 < best)) best = sub + 1;
      }
      return best;
    }

    return fewest(amount) ?? -1;
  }
}

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

Each remainder has one fixed answer, so cache it in a Map<int, int?>. A lookup of a missing key also returns null, the same as a stored "cannot be paid", so the cache test is memo.containsKey(rest) rather than a null check. The local function captures memo, so only amount + 1 calls do real work, each looping over the coins once.

class Solution {
  int coinChange(List<int> coins, int amount) {
    // memo[rest] holds null when rest cannot be paid
    final memo = <int, int?>{};

    int? fewest(int rest) {
      if (rest == 0) return 0;
      if (rest < 0) return null;
      if (memo.containsKey(rest)) return memo[rest];
      int? best;
      for (final c in coins) {
        final sub = fewest(rest - c);
        if (sub != null && (best == null || sub + 1 < best)) best = sub + 1;
      }
      return memo[rest] = best;
    }

    return fewest(amount) ?? -1;
  }
}

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Fill the memo in order instead. best[a] is the fewest coins that make a: List<int>.filled(amount + 1, tooMany) starts every slot one above any real answer and best[0] = 0 sets the base case. Walking a upward, every smaller entry is final, so each coin that fits offers best[a - c] + 1 and min from dart:math keeps the lowest. No recursion and no map hashing.

import 'dart:math';

class Solution {
  int coinChange(List<int> coins, int amount) {
    final tooMany = amount + 1; // more coins than any real answer can use
    final best = List<int>.filled(amount + 1, tooMany); // best[a] = fewest coins that make a
    best[0] = 0;
    for (var a = 1; a <= amount; a++) {
      for (final c in coins) {
        if (c <= a) best[a] = min(best[a], best[a - c] + 1);
      }
    }
    return best[amount] == tooMany ? -1 : best[amount];
  }
}

3 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every coin recursively

O(kⁿ) time · O(n) space

Whatever coin c goes first, the rest is the same problem for rest - c. A nested def fewest(rest: Int): Option[Int] returns None for a remainder that cannot be paid, so the whole step is one expression: coins.flatMap keeps only the payable remainders, minOption picks the best (or None) and map(_ + 1) counts the coin just taken. getOrElse(-1) produces the required -1. Correct, but the same remainders are solved again on every branch: 205 calls for coins [1, 5, 6, 9] and amount 11, 72,813 for 27.

object Solution {
  def coinChange(coins: Array[Int], amount: Int): Int = {
    // None means rest cannot be paid
    def fewest(rest: Int): Option[Int] =
      if (rest == 0) Some(0)
      else if (rest < 0) None
      else coins.flatMap(c => fewest(rest - c)).minOption.map(_ + 1)

    fewest(amount).getOrElse(-1)
  }
}

2 · Top-down: cache each remainder

O(n·k) time · O(n) space

Each remainder has one fixed answer, so cache it in a mutable.HashMap[Int, Option[Int]]. memo.getOrElseUpdate(rest, …) returns the stored value or evaluates the by-name argument once and stores it, None included, so the recursion body is the same expression as before. The map is created per call, so different coin sets never share results, and only amount + 1 remainders are ever computed.

import scala.collection.mutable

object Solution {
  def coinChange(coins: Array[Int], amount: Int): Int = {
    // memo(rest) is None when rest cannot be paid
    val memo = mutable.HashMap.empty[Int, Option[Int]]

    def fewest(rest: Int): Option[Int] =
      if (rest == 0) Some(0)
      else if (rest < 0) None
      else memo.getOrElseUpdate(rest, coins.flatMap(c => fewest(rest - c)).minOption.map(_ + 1))

    fewest(amount).getOrElse(-1)
  }
}

3 · Bottom-up: fill a table from 0 to amount

O(n·k) time · O(n) space

recommended

Fill the memo in order instead. best(a) is the fewest coins that make a: Array.fill(amount + 1)(tooMany) starts every slot one above any real answer and best(0) = 0 sets the base case. A single for with a guard, a <- 1 to amount; c <- coins if c <= a, visits every coin that fits, and math.min keeps the lowest offer best(a - c) + 1. The loop never returns early, so no boundary is needed, and 1 to 0 is simply empty for an amount of 0.

object Solution {
  def coinChange(coins: Array[Int], amount: Int): Int = {
    val tooMany = amount + 1 // more coins than any real answer can use
    val best = Array.fill(amount + 1)(tooMany) // best(a) = fewest coins that make a
    best(0) = 0
    for (a <- 1 to amount; c <- coins if c <= a) {
      best(a) = math.min(best(a), best(a - c) + 1)
    }
    if (best(amount) == tooMany) -1 else best(amount)
  }
}

FAQ for JavaScript

Why not just take the largest coin that fits each time?

That greedy rule is only safe for coin systems built for it. Sorting [1, 5, 6, 9] with toSorted((x, y) => y - x) and subtracting greedily pays 11 as 9, 1, 1, which is 3 coins against the 2 the table finds. With [2, 5, 10] and 23 it is worse: after 10 and 10 the leftover 3 cannot be paid, so greedy reports -1, while the table finds 6 coins (10, 5 and four 2s).

Why use Infinity instead of amount + 1 to mark impossible amounts?

Both work, but in JavaScript Infinity is just another number, so the array stays all numbers and the comparisons need no special case. On the engine Infinity + 1 === Infinity prints true, which means adding a coin to an unreachable amount stays unreachable, and Math.min() with no arguments even returns Infinity. Remember to turn it into -1 before returning, since that is what the caller expects.

How do I count the number of ways instead, and when does BigInt matter?

Swap the minimum for a sum and put the coin loop on the outside so each combination counts once: start with ways[0] = 1, then for each coin c do ways[a] += ways[a - c] for a from c up. Coins [1, 5, 6, 9] and 11 give 6. The counts grow fast: with [1, 2, 5, 10, 20, 50, 100, 200] an amount of 10000 gives 1133873304647601, still exact, but 20000 prints 135830481354545200 while a BigInt table (seeded with 1n and 0n) gives 135830481354545201n. Past Number.MAX_SAFE_INTEGER the low digits are rounded, not wrapped.

Why does the memoized version throw RangeError for large amounts?

Each coin of 1 adds a stack frame, so the depth grows with the amount. On our Node 26 engine a fresh call with coins [1, 5, 6, 9] returns 500 for 4500 but throws RangeError: Maximum call stack size exceeded for 5000. Treat that cutoff as approximate: it shifts with frame size and with how warmed-up the function is. The bottom-up table has no depth at all and returns 11112 for an amount of 100000.

How do I return the coins themselves, not just the count?

Keep a second array last and set last[a] = c whenever coin c improves best[a]. Then walk back from the amount, pushing last[a] and subtracting it until you reach 0. That yields [5,6] for 11 with [1, 5, 6, 9], and [2,5,10,10] for 27 with [2, 5, 10] once sorted with toSorted((x, y) => x - y). Without the comparator, sort compares strings and gives [ 10, 10, 2, 5 ].

FAQ for Java

Why can a largest-coin-first loop give the wrong answer?

Greedy is only safe for coin systems built for it, such as 1, 2, 5 and 10. For new int[] {1, 5, 6, 9} and 11, a loop that keeps subtracting the largest coin that fits spends 9, 1 and 1 (three coins) where 6 + 5 needs two. For {2, 5, 10} and 23 it gets stuck: two tens leave 3, which neither 2 nor 5 can cover, so greedy reports failure although 10, 5 and four 2s work; the table returns 6 there.

Why does the memoized version throw StackOverflowError?

The first path the recursion explores keeps taking the 1 coin, so it nests roughly amount calls deep before anything returns. Each call is a frame on the thread stack, and the JVM sizes that stack at startup; here it is -Xss512k. With {1, 5, 6, 9}, amount 3,000 returns 334 and amount 4,000 throws. The breaking point between the two shifts from run to run, because frames get smaller once the JIT compiles the method. Catching the error works but is fragile; the bottom-up table is the real fix and returns 11112 for 100,000. To keep the recursion anyway, start it on new Thread(null, task, "deep", 256L << 20), a thread with a 256 MB stack, which also returns 11112 for 100,000.

Can I use Integer.MAX_VALUE as infinity in the table?

Only with a guard. int arithmetic wraps without warning, so Integer.MAX_VALUE + 1 becomes -2147483648, and that negative number beats every real count in the < test. Leave the guard out and coins {4, 6} with amount 9 come back as -2147483648 rather than -1. Check best[a - c] != Integer.MAX_VALUE before adding, or pick a sentinel like amount + 1 that has room to grow. If you would rather fail loudly, Math.addExact throws an ArithmeticException instead of wrapping.

How do I count the ways to make the amount in Java?

Sum instead of minimising, with the coins in the outer loop so that 5 then 6 and 6 then 5 are one combination: long[] ways = new long[amount + 1]; ways[0] = 1; then, per coin c, for (int a = c; a <= amount; a++) ways[a] += ways[a - c];. For {1, 5, 6, 9} and 11, ways[11] is 6. Start with long because an int count overflows silently, and for really large inputs move to BigInteger or count modulo a prime.

How do I list the coins in the optimal answer?

Add an int[] pick of the same length and write pick[a] = c whenever coin c lowers best[a]. If the result is not -1, step down from the amount with for (int a = amount; a > 0; a -= pick[a]) chosen.add(pick[a]);, where chosen is an ArrayList<Integer> (each int is boxed on the way in). {1, 5, 6, 9} with 11 produces [5, 6]; {2, 5, 10} with 27 produces [2, 5, 10, 10] after Collections.sort(chosen).

FAQ for Go

Why does picking the biggest coin first fail?

Largest-first is only guaranteed for coin systems built for it, like 1, 2, 5 and 10. Try []int{1, 5, 6, 9} with 11: greedy hands over 9 and then two 1s, three coins, yet 5 and 6 do it in two. With []int{2, 5, 10} and 23 it fails outright: after two 10s the remaining 3 cannot be paid with 2 or 5, so greedy gives up, while the table finds 6 coins (10, 5 and four 2s).

Does deep recursion overflow the stack in Go?

Not at these sizes. A goroutine stack starts at a few kilobytes and the runtime moves it to a bigger block whenever it fills, up to a default ceiling of 1 GB on 64-bit platforms (debug.SetMaxStack from runtime/debug adjusts it). The memoised closure, unchanged, returns 11112 for coins []int{1, 5, 6, 9} and amount 100,000, and 111112 for 1,000,000. Go past the ceiling and the process stops with fatal error: stack overflow; that is not a panic, so recover cannot save it. The table version avoids the question entirely, and for very large amounts you can shrink the work by dividing the amount and every coin by their GCD, returning -1 early when the GCD does not divide the amount.

Should the memo be a map or a slice in Go?

Use the slice when nearly every remainder from 0 to amount comes up, which is the usual case once a coin of 1 is present: indexing is cheaper than hashing and the memory is one int per amount. Switch to map[int]int when the coins are large and only a handful of remainders are ever reached. The comma-ok form v, ok := memo[rest] then replaces the -2 marker, because a missing key reports ok == false instead of a zero value that could pass for an answer.

How do I count the ways to make the amount in Go?

Swap the minimum for a sum and put the coins in the outer loop, so 5 then 6 and 6 then 5 count as one combination: ways := make([]int, amount+1), ways[0] = 1, and for each coin c run for a := c; a <= amount; a++ { ways[a] += ways[a-c] }. Coins []int{1, 5, 6, 9} give ways[11] == 6. Go's int is 64 bits on this engine, which buys headroom, but counts still outgrow it on big inputs and wrap without an error; reach for math/big or take a modulus.

How do I get the actual coins back in Go?

Record the winning coin per amount in a parallel slice, choice := make([]int, amount+1), setting choice[a] = c inside the if that lowers best[a]. When the result is not -1, rebuild by stepping down: for a := amount; a > 0; a -= choice[a] { picked = append(picked, choice[a]) }, starting from a nil picked that append grows as needed. []int{1, 5, 6, 9} with 11 yields [5 6]; []int{2, 5, 10} with 27 yields [2 5 10 10] once passed through slices.Sort.

FAQ for C#

Why does taking the largest coin first give the wrong answer?

Greedy only works for coin systems designed for it, such as 1, 2, 5 and 10. For new[] { 1, 5, 6, 9 } and 11, a loop that keeps subtracting the largest coin that fits spends 9, 1 and 1 (three coins) where 6 + 5 needs two. With { 2, 5, 10 } and 23 it gets stuck: two tens leave 3, which neither 2 nor 5 covers, so greedy reports failure although 10, 5 and four 2s work; the table returns 6 there.

Why can I not catch the StackOverflowException from the memoized version?

The recursion nests roughly one frame per coin taken, and the first path it explores keeps taking the smallest coin, so a large amount with a coin of 1 goes about amount frames deep. A thread's stack size is fixed when the thread starts, and since .NET Core a StackOverflowException is not catchable: the runtime prints the trace and terminates the process, so a try / catch around the call does nothing. The bottom-up table is the real fix and returns 11112 for { 1, 5, 6, 9 } at 100,000. To keep the recursion anyway, run it on new Thread(work, 256 * 1024 * 1024), whose second argument is the stack size in bytes, and Join it.

Can I use int.MaxValue as infinity in the table?

Only with a guard. C# integer arithmetic wraps silently outside a checked block, so int.MaxValue + 1 becomes -2147483648, and that negative number beats every real count in the < test: coins { 4, 6 } with amount 9 would come back as -2147483648 instead of -1. Either test best[a - c] != int.MaxValue before adding, or pick a sentinel with room to grow such as amount + 1. Wrapping the addition in checked(...) makes it throw an OverflowException rather than wrap, which at least fails loudly.

How do I count the ways to make the amount instead?

Sum instead of minimising, with the coins in the outer loop so that 5 then 6 and 6 then 5 count as one combination: var ways = new long[amount + 1]; ways[0] = 1; then, per coin c, for (int a = c; a <= amount; a++) ways[a] += ways[a - c];. For { 1, 5, 6, 9 } and 11, ways[11] is 6. Use long from the start because an int count overflows silently; for very large inputs switch to System.Numerics.BigInteger or count modulo a prime.

How do I return the coins in the optimal answer?

Keep an int[] pick of the same length and set pick[a] = c whenever coin c lowers best[a]. If the result is not -1, walk down from the amount: var chosen = new List<int>(); for (int a = amount; a > 0; a -= pick[a]) chosen.Add(pick[a]);. { 1, 5, 6, 9 } with 11 gives [5, 6], and { 2, 5, 10 } with 27 gives [2, 5, 10, 10] after chosen.Sort().

FAQ for Kotlin

Why does taking the largest coin first fail?

Greedy only works for coin systems designed for it, such as 1, 2, 5 and 10. With intArrayOf(1, 5, 6, 9) and 11, coins.sortedDescending() plus repeated subtraction spends 9, 1 and 1 (three coins) while 5 + 6 needs two. With intArrayOf(2, 5, 10) and 23 it takes 10 and 10 and is stuck at 3, although 10, 5 and four 2s make six coins.

Can a local fun call itself recursively?

Yes. A local fun declared inside coinChange is in scope in its own body, so it can recurse, and it captures coins and memo from the enclosing function. A lambda stored in a val cannot refer to itself, which is why the solutions use a local fun instead.

Why does 1..amount work when the amount is 0?

1..0 is an empty range in Kotlin, so the loop body never runs and best[0] (0) is returned. Ranges only count upward; a downward walk needs downTo.

Can I use Int.MAX_VALUE as the "unreachable" value?

Only with a guard. Int arithmetic wraps silently, so Int.MAX_VALUE + 1 becomes Int.MIN_VALUE, which wins every minOf. Coins intArrayOf(4, 6) with amount 9 would then return a large negative number instead of -1. Check best[a - c] != Int.MAX_VALUE before adding, or use amount + 1, which has room to grow.

How do I count the ways to make the amount instead?

Sum instead of minimising, with the coin loop outside so each combination is counted once: val ways = LongArray(amount + 1).also { it[0] = 1 }, then for (c in coins) for (a in c..amount) ways[a] += ways[a - c]. For coins [1, 5, 6, 9] and amount 11, ways[11] is 6. LongArray keeps larger counts from overflowing an Int.

Keep going

Number of Islands24 / 40 · Graphs · Medium

Try Coin Change in Python (Coin Change in Python), JavaScript (Coin Change in JavaScript), TypeScript (Coin Change in TypeScript), Java (Coin Change in Java), Go (Coin Change in Go), C# (Coin Change in C#), C++ (Coin Change in C++), C (Coin Change in C), Rust (Coin Change in Rust), Swift (Coin Change in Swift), PHP (Coin Change in PHP), Ruby (Coin Change in Ruby), Dart (Coin Change in Dart) or Scala (Coin Change in Scala) instead.

coin_change.kt

Kotlin 2.4

Not run yet

+ 7 hidden

Input

coins = [1, 5, 6, 9]
amount = 11

Expected

5 + 6 pays 11 with two coins. Taking the largest coin first gives 9 + 1 + 1, three coins.