Coin Change

The problem

You are given a list of coin values coins and a target amount. You have as many coins of each value as you like. Return the fewest coins that add up to exactly amount, or -1 if no mix of coins does.

Example 1

Input: coins = [1, 3, 4], amount = 6

Output: 2

3 + 3 = 6. Taking the biggest coin first gives 4 + 1 + 1, which uses 3 coins.

coins

134

Example 2

Input: coins = [2], amount = 3

Output: -1

Twos only make even amounts.

Example 3

Input: coins = [5], amount = 0

Output: 0

Nothing to pay, so no coins.

Constraints

• 1 ≤ coins.length ≤ 12 (call it c)
• 1 ≤ coins[i] ≤ 2³¹ − 1, all different
• 0 ≤ amount ≤ 10,000 (call it A)

Clarifying questions

Can a coin be used more than once?

Yes, as many times as we like.

Do we return the coins or how many?

Only how many.

What if the amount is 0?

Return 0. No coins are needed.

Does taking the biggest coin first work?

No. Example 1 shows it giving 3 coins when 2 are enough.

Spot the pattern

Look at the last coin in the best answer. Whatever it is, the coins before it must be the best way to make the amount minus that coin. So the answer for an amount is built from answers for smaller amounts, and the same smaller amounts come up again and again. That is dynamic programming. Greedy fails, as Example 1 shows, so we really have to compare every coin.

Solutions

Plain recursionO(c^(A/m))Table, bottom upO(A × c)

Show all

There is no middle tab. Adding a memo to the recursion gives the same O(A × c) time as the table, with a deep call stack on top, so the table is shown instead.

Plain recursion O(c^(A/m))

The idea

Let fewest(left) be the fewest coins that make left. If left is 0, it is 0. Otherwise, try every coin that fits as the next coin: that uses 1 coin, and fewest(left - coin) more. Keep the smallest. If no coin works, the result is infinity, which means impossible, and the final answer is −1.

Why it is correct: every way to pay starts with some coin, and the recursion tries every coin first, then the best way to pay the rest.

Walkthrough

fewest(left)

0123456

calls so far

0

1. def fewest(left):
2. if left == 0: return 0
3. best = infinity
4. for coin in coins:
5. if coin <= left: best = min(best, 1 + fewest(left - coin))
6. return best
7. answer = fewest(amount), or -1 if it is infinity

fewest(left) is the fewest coins that make the amount left. Try each coin as the next one: 1 + fewest(left − coin). Start with fewest(6). The row below fills in as calls return.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private static final int NONE = Integer.MAX_VALUE;
    private int[] coins;

    // Plain recursion: try every coin as the next one and solve what is left.
    // The same amounts left are solved again and again, so the work grows exponentially.
    public int coinChange(int[] coins, int amount) {
        this.coins = coins;
        int answer = fewest(amount);
        // NONE means no mix of coins hits the amount exactly.
        return answer == NONE ? -1 : answer;
    }

    private int fewest(int left) {
        if (left == 0) return 0;
        int best = NONE;
        for (int coin : coins) {
            // A coin bigger than what is left would overshoot.
            if (coin <= left) {
                int fewestRest = fewest(left - coin);
                if (fewestRest != NONE) best = Math.min(best, 1 + fewestRest);
            }
        }
        return best;
    }
}

Big O

Time O(c^(A/m))Space O(A)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The work repeats through recursion, so we count the calls of fewest. Each call loops over the c coins and starts one call per coin that fits.

   1. def fewest(left):
   2. if left == 0: return 0
   3. best = infinity
   4. for coin in coins:
   5. if coin <= left: best = min(best, 1 + fewest(left - coin))
   6. return best
   7. answer = fewest(amount), or -1 if it is infinity

2. 2 Count the runs on Example 1

   The table counts calls by the amount left. Small amounts are reached along many paths: fewest(0) is called 9 times.

   1 + 1 + 1 + 2 + 4 + 6 + 9 = 24 calls, for only 7 different amounts.

   left	6	5	4	3	2	1	0
   fewest() calls	1	1	1	2	4	6	9

   total

   1 + 1 + 1 + 2 + 4 + 6 + 9 = 24 calls

3. 3 Write the count for any n

   Call the smallest coin m. Each call takes at least m off, so a path of calls is at most A / m long. Each call starts at most c more:

   1 + c + c² + … + c^(A/m) calls

   Check it with Example 1: c = 3 and A / m = 6, so up to 1 + 3 + 9 + … + 729 = 1093 calls. The real run made 24, because big coins overshoot small amounts.

4. 4 Keep only the part that grows fastest

   The last term is bigger than all the others together, so the sum is less than 2 × c^(A/m). Drop the 2. Each call also runs a loop of c coins, one more factor of c, which does not change the picture: the time is exponential, about c^(A/m). With A = 10,000 and a coin of 1, hopeless.

   So the time is O(c^(A/m)).

5. S Space: count the extra memory the same way

   The call stack holds one path, at most A / m calls, which is at most A. So the space is O(A).

   call stack (up to amount deep)

Table, bottom up O(A × c)

The idea

There are only A + 1 different amounts the recursion can ask about: 0 to A. So answer each one once, from the bottom up, in a table.

fewest[0] = 0. Every other slot starts as “impossible”. For each amount sub_amount from 1 to A, try each coin as the last coin: if it fits, fewest[sub_amount - coin] + 1 is one way to make sub_amount. Keep the smallest. Since sub_amount - coin is smaller than sub_amount, its slot is already final.

In code, “impossible” is the number A + 1. No answer can need more than A coins, since every coin is at least 1, so A + 1 is safely too big and still adds without overflowing.

Why it is correct: the best way to make sub_amount ends with some coin, and the coins before it are the best way to make sub_amount - coin. The loop tries every last coin, and each fewest[sub_amount - coin] is already the best.

Walkthrough

fewest

00∞1∞2∞3∞4∞5∞6

1. fewest = [0] + [infinity] * amount
2. for sub_amount in 1 .. amount:
3. for coin in coins:
4. if coin <= sub_amount:
5. fewest[sub_amount] = min(fewest[sub_amount], fewest[sub_amount - coin] + 1)
6. return fewest[amount], or -1 if it is infinity

Build a table from the bottom. fewest[sub_amount] is the fewest coins that make sub_amount. fewest[0] = 0, and the rest start as ∞, meaning "not possible yet". Coins: 1, 3, 4.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Table, bottom up: fewest[subAmount] is the fewest coins that make subAmount. Build it
    // from 0 up, so every smaller amount is ready. O(amount × coins) time, O(amount) space.
    public int coinChange(int[] coins, int amount) {
        // amount + 1 coins is more than any real answer, so it works as "impossible".
        int[] fewest = new int[amount + 1];
        java.util.Arrays.fill(fewest, amount + 1);
        fewest[0] = 0;
        for (int subAmount = 1; subAmount <= amount; subAmount++) {
            for (int coin : coins) {
                // Use this coin last, on top of the best way to make subAmount - coin.
                if (coin <= subAmount)
                    fewest[subAmount] = Math.min(fewest[subAmount], fewest[subAmount - coin] + 1);
            }
        }
        return fewest[amount] <= amount ? fewest[amount] : -1;
    }
}

Big O

Time O(A × c)Space O(A)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The inner loop body does one check, an addition and a min. That is a fixed job, so each run of the inner loop counts as 1 step.

   1. fewest = [0] + [infinity] * amount
   2. for sub_amount in 1 .. amount:
   3. for coin in coins:
   4. if coin <= sub_amount:
   5. fewest[sub_amount] = min(fewest[sub_amount], fewest[sub_amount - coin] + 1)
   6. return fewest[amount], or -1 if it is infinity

2. 2 Count the runs on Example 1

   The table has one column per amount. Each amount tries all 3 coins, even the ones too big to fit.

   6 × 3 = 18 runs.

   sub_amount	1	2	3	4	5	6
   coins tried	3	3	3	3	3	3

   total

   6 × 3 = 18 inner runs

3. 3 Write the count for any n

   The outer loop runs A times, and the inner loop runs c times for each:

   A × c runs

   Check it with Example 1: 6 × 3 = 18. That matches the count.

4. 4 Keep only the part that grows fastest

   Nothing to drop. It is O(A × c): at most 10,000 × 12 = 120,000 steps.

   So the time is O(A × c).

5. S Space: count the extra memory the same way

   The table has A + 1 slots. So the space is O(A).

   fewest table (amount + 1)

Common mistake

Using the largest number as infinity

If “impossible” is stored as the biggest integer, then fewest[sub_amount - coin] + 1 overflows to a negative number in Java, C# and Go, and wins every min. Use A + 1 instead, or check for “impossible” before adding.

Tested at the limits

2,000 random inputs of 1 to 3 coins from 1 to 7 and an amount from 0 to 9. Amount 0 and cases with no answer, like even coins and an odd amount, come up. The plain recursion and the table gave the same answer every time.

Largest inputs	Result
Amount 10,000 with 12 coins (the most allowed), answer 234 coins. Table, bottom up.	0.01 s, and about 0.15 MB of extra memory: one list of 10,001 counts, O(A).
Amount 9,999 with 12 even coins: no answer, so the table never fills in. Table, bottom up.	0.01 s, about 0.15 MB of extra memory, and −1, as it should be.