Coin Change: Fewest Coins

Given coin values and an amount, return the fewest coins that add up to the amount, using any number of coins of each value. Return OptionalInt.empty() if the amount can't be made. OptionalInt is a container that holds either one int or nothing, so a method can report "no answer" without a sentinel such as -1.

LeetCode: 322. Coin Change

Example

Text

coins = [2, 3, 5, 6], amount = 10  ->  2       (5 + 5)
coins = [1, 2, 3],    amount = 3   ->  1       (3)
coins = [2],          amount = 3   ->  empty

Taking the largest coin first doesn't work: with coins [1, 3, 4] and amount 6, greedy picks 4 + 1 + 1 (3 coins), but 3 + 3 needs only 2.

Brute force: try every coin as the next one

The fewest coins for amount is one coin plus the fewest coins for what's left, minimized over every choice of that coin:

Text

fewest(0) = 0
fewest(a) = 1 + min over coins c <= a of fewest(a - c)

Java

import java.util.OptionalInt;

public class Main {
    static OptionalInt fewest(int[] coins, int amount) {
        if (amount == 0) return OptionalInt.of(0);
        int best = Integer.MAX_VALUE;
        for (int c : coins) {
            if (c <= amount) {
                OptionalInt sub = fewest(coins, amount - c);
                if (sub.isPresent()) best = Math.min(best, sub.getAsInt() + 1);
            }
        }
        return best == Integer.MAX_VALUE ? OptionalInt.empty() : OptionalInt.of(best);
    }

    public static void main(String[] args) {
        System.out.println(fewest(new int[]{2, 3, 5, 6}, 10) + " " + fewest(new int[]{1, 2, 3}, 3) + " " + fewest(new int[]{2}, 3));
    }
}

Output

OptionalInt[2] OptionalInt[1] OptionalInt.empty

Time: O(kᵃ) in the worst case for k coins and amount a: the same remaining amounts are solved over and over. Space: O(a) for the recursion.

Optimal: a table over all amounts

The recursion only ever asks about amounts from 0 to amount. Compute them all once, in increasing order, so every fewest(a - c) is already known when fewest(a) needs it.

amount	0	1	2	3	4	5	6	7	8	9	10
fewest	0	–	1	1	2	1	1	2	2	2	2

The table is an int[] where -1 marks an amount that can't be made. The sentinel stays inside the method; the method returns an OptionalInt.

Java

import java.util.Arrays;
import java.util.OptionalInt;

public class Main {
    static OptionalInt fewest(int[] coins, int amount) {
        int[] best = new int[amount + 1];
        Arrays.fill(best, -1); // -1: not reachable
        best[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a && best[a - c] != -1) {
                    int candidate = best[a - c] + 1;
                    if (best[a] == -1 || candidate < best[a]) best[a] = candidate;
                }
            }
        }
        return best[amount] == -1 ? OptionalInt.empty() : OptionalInt.of(best[amount]);
    }

    public static void main(String[] args) {
        System.out.println(fewest(new int[]{2, 3, 5, 6}, 10) + " " + fewest(new int[]{1, 2, 3}, 3) + " " + fewest(new int[]{2}, 3));
        System.out.println(fewest(new int[]{1, 3, 4}, 6) + " " + fewest(new int[]{186, 419, 83, 408}, 6249));
        System.out.println(fewest(new int[]{5}, 0));
    }
}

Output

OptionalInt[2] OptionalInt[1] OptionalInt.empty
OptionalInt[2] OptionalInt[20]
OptionalInt[0]

Time: O(a · k). Space: O(a).

The -1 sentinel avoids Integer.MAX_VALUE + 1, which would wrap to a negative number.

Edge cases

Amount 0: OptionalInt.of(0).
No combination works: OptionalInt.empty().
Counting the ways instead (LeetCode 518): loop over coins in the outer loop and amounts in the inner loop, and add instead of taking the minimum, so each combination is counted once regardless of order.