SyntaxPilot
Courses/DSA and Coding Problems/Lesson 64
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 64 of 90

Coin change: fewest coins and number of ways

queued

These are the notes for DSA episode 64. A parcel needs ₹6 of postage and the counter has ₹1, ₹3 and ₹4 stamps. The clerk's habit, biggest stamp first, gives 4 + 1 + 1 = 3 stamps, but 3 + 3 needs only 2. We watch greedy fail live (3 instead of 2, and -1 for amount 6 with coins [2, 5] although 2 + 2 + 2 works), write the correct recursion (try every last coin: Time Limit Exceeded for amount 100), and build the DP table dp[a] = min over c of dp[a - c] + 1. Then Coin Change II counts the ways, where the order of the two loops decides whether we count combinations or orders. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real.

The problem, in real life

At the post office In code
Stamp values ₹1, ₹3, ₹4 (plenty of each) coins = {1, 3, 4}
Postage needed: ₹6 amount = 6
Fewest stamps Coin Change (LeetCode 322)
Number of different stamp combinations Coin Change II (LeetCode 518)

With India's coins and notes (1, 2, 5, 10, 20, 50, …) biggest-first always gives the fewest; such coin systems are called canonical. With other sets (1, 3, 4) it can fail.

Every word, from zero

  • Unbounded supply: each coin value can be used any number of times.
  • Greedy (biggest first): take the largest coin that fits, repeat.
  • Canonical coin system: one where greedy always gives the fewest coins.
  • State: dp[a] = fewest coins to make amount a (part 1), or the number of ways to make a (part 2).
  • Recurrence from the last coin: if the last coin is c, the rest is amount a - c.
  • Sentinel ("impossible" marker): a value that can never be a real answer; here amount + 1.
  • Combination vs permutation (order): {1, 2, 2} counted once vs 1+2+2, 2+1+2, 2+2+1 counted separately.
  • Integer overflow: Integer.MAX_VALUE + 1 wraps to Integer.MIN_VALUE (−2,147,483,648).

Problem statement

LeetCode 322, Coin Change. Return the fewest coins that make up amount, or -1 if impossible.

coins amount Answer
[1, 2, 5] 11 3 (5 + 5 + 1)
[2] 3 -1
[1] 0 0

Constraints: 1 ≤ coins.length ≤ 12, 1 ≤ coins[i] ≤ 2^31 - 1, 0 ≤ amount ≤ 10^4.

Greedy fails: biggest coin first

import java.util.*;

public class Main {
    static int coinChange(int[] coins, int amount) {
        int[] c = coins.clone();
        Arrays.sort(c);
        int count = 0;
        for (int i = c.length - 1; i >= 0; i--)
            while (amount >= c[i]) {
                amount -= c[i];
                count++;
            }
        return amount == 0 ? count : -1;
    }
    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11));
        System.out.println(coinChange(new int[]{2}, 3));
        System.out.println(coinChange(new int[]{1}, 0));
        System.out.println(coinChange(new int[]{1, 3, 4}, 6));
        System.out.println(coinChange(new int[]{2, 5}, 6));
    }
}
3
-1
0
3
-1

[1, 3, 4], 6 → greedy 3 (4+1+1), best 2 (3+3). [2, 5], 6 → greedy takes 5 and is stuck at 1: -1, but 2 + 2 + 2 works.

Obvious correct idea: try every last coin

import java.util.*;

public class Main {
    static int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        int best = -1;
        for (int c : coins)
            if (c <= amount) {
                int sub = coinChange(coins, amount - c);
                if (sub != -1 && (best == -1 || sub + 1 < best)) best = sub + 1;
            }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11));
        System.out.println(coinChange(new int[]{2}, 3));
        System.out.println(coinChange(new int[]{1}, 0));
        System.out.println(coinChange(new int[]{1, 3, 4}, 6));
    }
}
3
-1
0
2

Amount 100 with [1, 2, 5]: Time Limit Exceeded. Every amount branches three ways, the depth can reach 100, and the same smaller amounts are solved over and over.

The key insight: the DP table

  1. State: dp[a] = fewest coins for amount a.
  2. Recurrence: dp[a] = min over coins c ≤ a of dp[a - c] + 1.
  3. Base: dp[0] = 0; every other cell starts at amount + 1 = impossible (you never need more than amount coins, even with ₹1 coins).
  4. Order: a = 1 … amount; answer -1 if dp[amount] > amount.

By hand, stamps [1, 3, 4], amount 6:

a 0 1 2 3 4 5 6
dp[a] 0 1 2 1 1 2 2

dp[6] = min(dp[5] + 1, dp[3] + 1, dp[2] + 1) = min(3, 2, 3) = 2.

Solution in Java: fewest coins

import java.util.*;

public class Main {
    static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++)
            for (int c : coins)
                if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
        return dp[amount] > amount ? -1 : dp[amount];
    }
    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11));
        System.out.println(coinChange(new int[]{2}, 3));
        System.out.println(coinChange(new int[]{1}, 0));
        System.out.println(coinChange(new int[]{1, 3, 4}, 6));
        System.out.println(coinChange(new int[]{2, 5}, 6));
        System.out.println(coinChange(new int[]{1, 2, 5}, 100));
        System.out.println(coinChange(new int[]{1, 2, 5, 10, 20, 50, 100, 200, 500, 2000}, 10000));
        System.out.println(coinChange(new int[]{7, 13}, 9999));
    }
}
3
-1
0
2
3
20
5
771

(c <= a also protects against huge coin values like 2^31 - 1: they're never subtracted.)

Top-down: the recursion plus a notebook

-1 is a real answer (impossible), so -2 marks "not known yet".

import java.util.*;

public class Main {
    static int[] memo;
    static int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        Arrays.fill(memo, -2);
        return fewest(coins, amount);
    }
    static int fewest(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (memo[amount] != -2) return memo[amount];
        int best = -1;
        for (int c : coins)
            if (c <= amount) {
                int sub = fewest(coins, amount - c);
                if (sub != -1 && (best == -1 || sub + 1 < best)) best = sub + 1;
            }
        memo[amount] = best;
        return best;
    }
    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11));
        System.out.println(coinChange(new int[]{2}, 3));
        System.out.println(coinChange(new int[]{1}, 0));
        long t0 = System.nanoTime();
        int n = coinChange(new int[]{1, 2, 5}, 100);
        System.out.println(n + " coins, " + (System.nanoTime() - t0) / 1000000 + " ms");
    }
}
3
-1
0
20 coins, 0 ms

Which coins? Remember the last coin of every amount

import java.util.*;

public class Main {
    static void plan(int[] coins, int amount) {
        int[] dp = new int[amount + 1], last = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++)
            for (int c : coins)
                if (c <= a && dp[a - c] + 1 < dp[a]) {
                    dp[a] = dp[a - c] + 1;
                    last[a] = c;
                }
        List<Integer> used = new ArrayList<>();
        for (int a = amount; a > 0; a -= last[a]) used.add(last[a]);
        System.out.println(amount + " = " + used + ", " + dp[amount] + " coins");
    }
    public static void main(String[] args) {
        plan(new int[]{1, 3, 4}, 6);
        plan(new int[]{1, 3, 4}, 10);
        plan(new int[]{1, 2, 5, 10, 20, 50, 100, 200, 500, 2000}, 2789);
    }
}
6 = [3, 3], 2 coins
10 = [3, 3, 4], 3 coins
2789 = [2, 2, 5, 10, 20, 50, 200, 500, 2000], 9 coins

Part 2: Coin Change II (LeetCode 518), the number of ways

Return the number of combinations that make amount. dp[0] = 1 (the empty way).

amount coins Answer
5 [1, 2, 5] 4 (5 · 2+2+1 · 2+1+1+1 · 1+1+1+1+1)
3 [2] 0
10 [10] 1

Coins in the outer loop. Add one coin type at a time; each combination is built in one fixed order of coin types, so it's counted once:

after coin dp[0..5]
1 1 1 1 1 1 1
2 1 1 2 2 3 3
5 1 1 2 2 3 4
import java.util.*;

public class Main {
    static int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int c : coins)
            for (int a = c; a <= amount; a++)
                dp[a] += dp[a - c];
        return dp[amount];
    }
    public static void main(String[] args) {
        System.out.println(change(5, new int[]{1, 2, 5}));
        System.out.println(change(3, new int[]{2}));
        System.out.println(change(10, new int[]{10}));
        System.out.println(change(500, new int[]{1, 2, 5, 10, 20, 50, 100, 200, 500}));
    }
}
4
0
1
6295435

The same solutions in C++

#include <bits/stdc++.h>
using namespace std;

// Coin Change (LeetCode 322): fewest coins. Coin Change II (LeetCode 518): number of combinations.
int coinChange(const vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

long long change(int amount, const vector<int>& coins) {
    vector<long long> dp(amount + 1, 0);
    dp[0] = 1;
    for (int c : coins)
        for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
    return dp[amount];
}

int main() {
    cout << coinChange({1, 2, 5}, 11) << " " << coinChange({2}, 3) << " " << coinChange({1}, 0) << " "
         << coinChange({1, 3, 4}, 6) << " " << coinChange({2, 5}, 6) << "\n";
    cout << change(5, {1, 2, 5}) << " " << change(3, {2}) << " " << change(10, {10}) << "\n";
}
3 -1 0 2 3
4 0 1

The same solutions in Python

# Coin Change (LeetCode 322) and Coin Change II (LeetCode 518).
def coin_change(coins, amount):
    dp = [0] + [amount + 1] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return -1 if dp[amount] > amount else dp[amount]

def change(amount, coins):
    dp = [1] + [0] * amount
    for c in coins:                  # coins outside: combinations
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

print(coin_change([1, 2, 5], 11), coin_change([2], 3), coin_change([1], 0), coin_change([1, 3, 4], 6), coin_change([2, 5], 6))
print(change(5, [1, 2, 5]), change(3, [2]), change(10, [10]))
3 -1 0 2 3
4 0 1

Coin change is an unbounded knapsack

Every coin can be reused, which is why the inner loop runs upward (a = c … amount): dp[a - c] may already include coin c. If each item could be used only once, that's the 0/1 knapsack (next episode), where the loop direction changes.

Three real bugs

Bug 1: Integer.MAX_VALUE as "impossible"

Arrays.fill(dp, Integer.MAX_VALUE); on [2], amount 3:

-2147483648

dp[1] is MAX_VALUE, and dp[1] + 1 overflows to the most negative int, which then wins every min. Use amount + 1.

Bug 2: the loops swapped (amounts outside)

        for (int a = 1; a <= amount; a++)
            for (int c : coins)
                if (c <= a) dp[a] += dp[a - c];
9

9 instead of 4: now 1+2+2, 2+1+2 and 2+2+1 are different. That counts orders, which is a different problem: Combination Sum IV (LeetCode 377).

Bug 3: no "impossible" check

return dp[amount]; on [2], amount 3:

4

4 is the sentinel amount + 1 leaking out; LeetCode wants -1.

Complexity

k = number of coin values.

Approach Time Space Big input
Biggest first O(k log k + answer) O(k) wrong on some coin sets
Try every last coin exponential O(amount) stack amount 100: Time Limit Exceeded
DP fewest coins O(amount · k) O(amount) amount 10,000: 3 ms
DP number of ways O(amount · k) O(amount)

Common mistakes

Mistake What you see (real) Why Fix
Biggest coin first 3 instead of 2; -1 instead of 3 greedy fails on non-canonical coins DP over amounts
Fill with Integer.MAX_VALUE -2147483648 MAX_VALUE + 1 overflows amount + 1
Ways with amounts outside 9 instead of 4 counts orders coins in the outer loop
No impossible check 4 instead of -1 the sentinel leaks out > amount ? -1 : dp[amount]
dp[0] = 0 in the ways problem every answer 0 nothing to build from dp[0] = 1
int for many ways overflow on big amounts counts grow fast long (LeetCode 518 fits in int)

Mini project: which coins?

Remember the last coin used for each amount, then walk back from amount.

import java.util.*;

public class Main {
    // Mini project: fewest coins AND which coins, by remembering the last coin for every amount.
    public static void main(String[] args) {
        int[] coins = {1, 3, 4};
        int amount = 10;
        int[] dp = new int[amount + 1], last = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++)
            for (int c : coins)
                if (c <= a && dp[a - c] + 1 < dp[a]) { dp[a] = dp[a - c] + 1; last[a] = c; }
        List<Integer> used = new ArrayList<>();
        for (int a = amount; a > 0; a -= last[a]) used.add(last[a]);
        System.out.println("₹" + amount + " = " + used + " (" + dp[amount] + " stamps)");
    }
}
₹10 = [3, 3, 4] (3 stamps)

Practice

1. Perfect Squares (LeetCode 279). The fewest perfect squares (1, 4, 9, 16, …) that sum to n.

Solution

Coin change where the coins are the squares up to n.

# Perfect Squares (LeetCode 279): coin change with square coins.
def num_squares(n):
    squares = [k * k for k in range(1, int(n ** 0.5) + 1)]
    dp = [0] + [n + 1] * n
    for a in range(1, n + 1):
        for s in squares:
            if s > a:
                break
            dp[a] = min(dp[a], dp[a - s] + 1)
    return dp[n]

print(num_squares(12), num_squares(13), num_squares(1), num_squares(7))
3 2 1 4

2. Combination Sum IV (LeetCode 377). The number of ordered sequences that sum to target.

Solution

Exactly bug 2: amounts in the outer loop.

import java.util.*;

public class Main {
    // Combination Sum IV (LeetCode 377): counts orders, so amounts go in the outer loop.
    static int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int a = 1; a <= target; a++)
            for (int x : nums)
                if (x <= a) dp[a] += dp[a - x];
        return dp[target];
    }
    public static void main(String[] args) {
        System.out.println(combinationSum4(new int[]{1, 2, 3}, 4));
        System.out.println(combinationSum4(new int[]{9}, 3));
    }
}
7
0

3. Minimum Cost For Tickets (LeetCode 983). 1-day, 7-day and 30-day passes; cover all travel days for the least money. Hint: dp[d] = cheapest up to day d; on a travel day, min(dp[d-1] + c1, dp[d-7] + c7, dp[d-30] + c30).

Quick quiz

coins = [1, 5, 6, 9], amount = 11. Fewest coins? A) 2 B) 3 C) 4 D) -1

Answer

A) 2: 5 + 6. Biggest first takes 9 + 1 + 1 = 3.

Interview questions

  1. Why does greedy fail for coin change? Some coin systems aren't canonical: taking the biggest coin can force many small ones later ([1, 3, 4], 6).
  2. State and recurrence? dp[a] = min over c ≤ a of dp[a - c] + 1, dp[0] = 0.
  3. Why amount + 1 as infinity? It's larger than any real answer and doesn't overflow when you add 1.
  4. Combinations vs permutations in the ways problem? Coins outside → combinations (518); amounts outside → orders (377).
  5. Complexity? O(amount × k) time, O(amount) space.
  6. How is this related to knapsack? It's the unbounded knapsack: each item can be reused. Next episode: each item at most once (0/1 knapsack).

Glossary

Term Meaning
Unbounded supply Each coin can be used any number of times
Greedy (biggest first) Take the largest coin that fits
Canonical coin system Greedy always gives the fewest coins
State dp[a] = fewest coins / number of ways for amount a
Sentinel A value meaning "impossible" (amount + 1)
Combination Order doesn't matter
Permutation (order) Order matters
Integer overflow Past Integer.MAX_VALUE, an int wraps to negative
Unbounded knapsack Items reusable; coin change is one

Summary

  • Biggest-first change-giving fails on some coin sets ([1, 3, 4], 6 → 3 instead of 2).
  • Fewest coins: dp[a] = min(dp[a - c] + 1), dp[0] = 0, impossible = amount + 1, answer -1 if still impossible.
  • Number of ways: dp[0] = 1, dp[a] += dp[a - c], coins in the outer loop for combinations.
  • Both are O(amount × k). Watch for MAX_VALUE + 1, swapped loops and the missing -1.
  • Next episode: 0/1 knapsack: each item can be used only once.