Coin Change

Coin Change is the problem that proves greedy is not enough. It looks like something you could solve by always taking the biggest coin that fits — and for real currencies that often works — but for general coin sets it does not, and only a table finds the true answer.

It is also your first unbounded choice: each coin may be used as often as you like, which changes the transition from "look back one item" to "look back one coin".

The problem

You are given coin values and an amount. Using as many of each coin as you like, return the fewest coins that add up to the amount, or −1 if no mix of coins can make it.

• coins = [1, 3, 4], amount = 6 → 2. 3 + 3.
• coins = [5], amount = 3 → −1. 5 is already too big.
• amount = 0 → 0. No coins needed.

Constraints: 1 ≤ number of coins ≤ 12, 1 ≤ coin ≤ 2³¹ − 1, 0 ≤ amount ≤ 10⁴.

Clarifying questions

• Unlimited coins of each value? Yes.
• Can the amount be 0? Yes, and the answer is 0.
• Are coin values distinct and positive? Yes.
• Fewest coins, or the coins themselves? The count. Returning the coins is a follow-up.

Approach 1: the simple way — greedy, then plain recursion

The first idea is greedy: take the biggest coin that fits, repeat. With [1, 3, 4] and 6 it takes 4, then 1, then 1 — three coins. The best is 3 + 3, two coins. Greedy commits to the 4 and can never take it back. It works for coin sets like 1, 2, 5, 10, but not in general, so it is out.

The correct brute force tries every coin as the last coin and recurses on what remains:

1from math import inf23def coin_rec(coins: list[int], amount: int) -> int:4    """Fewest coins for amount, trying every coin as the last one."""5    def fewest(a: int) -> float:6        if a == 0:7            return 0                       # nothing left to pay8        best = inf                         # inf = "cannot be made"9        for c in coins:10            if c <= a:11                best = min(best, 1 + fewest(a - c))12        return best13    answer = fewest(amount)14    return -1 if answer == inf else int(answer)

Why it is too slow. Each call branches once per coin. With [1, 3, 4] it makes 24 calls for amount 6, 20,736 for amount 20 and 2,550,408 for amount 30. For amount 10⁴ it would never end. But there are only amount + 1 different questions — fewest(0) to fewest(amount) — so the calls repeat massively.

The key insight

The fewest coins for amount a does not care how you will later use it. Whatever the best way to make a is, its last coin is some c, and the coins before it must be the best way to make a − c — otherwise you could swap in a better way and beat the "best". So:

dp[a] = 1 + min(dp[a - c]  for every coin c with c <= a)dp[0] = 0,   and dp[a] = infinity if no coin leads to a reachable amount

The state is dp[a] = the fewest coins that make exactly a. The "infinity" is not decoration: it means "not reachable", and 1 + infinity stays infinity, so unreachable amounts never pollute reachable ones.

Approach 2: memoisation

1from functools import cache2from math import inf34def coin_memo(coins: list[int], amount: int) -> int:5    @cache6    def fewest(a: int) -> float:7        if a == 0:8            return 09        return min((1 + fewest(a - c) for c in coins if c <= a), default=inf)10    answer = fewest(amount)11    return -1 if answer == inf else int(answer)

Each amount is solved once. O(amount × coins) time. But the stack can be amount deep — with a coin of 1 and amount 10⁴ that is 10,000 nested calls, well past Python's default limit. That alone is a reason to tabulate here.

Approach 3: tabulation

1from math import inf23def coin_change(coins: list[int], amount: int) -> int:4    """Fewest coins that make amount, or -1. Coins can be reused."""5    dp = [0] + [inf] * amount            # dp[a] = fewest coins for amount a6    for a in range(1, amount + 1):7        for c in coins:8            if c <= a and dp[a - c] + 1 < dp[a]:9                dp[a] = dp[a - c] + 1    # use coin c last10    return -1 if dp[amount] == inf else int(dp[amount])

Fill amounts from 1 upward, because dp[a] reads only smaller amounts. For each amount, try each coin as the last one.

Dry run with [1, 3, 4], amount 6:

dp[6] = 2. At amount 6 the table compares all three "last coins" and finds that ending with a 3 on top of dp[3] = 1 is best — the option greedy never looked at.

Complexity: amount states × one check per coin = O(amount × coins) time, O(amount) space. For amount 10⁴ and 12 coins that is 120,000 steps.

What about stage 4?

Here the space saving does not apply, and it is worth saying so. The table is already one row, and dp[a] may read any earlier amount (a − 1, a − 4, a − 1,000…), not just the last one or two. There is nothing to throw away. O(amount) is the floor for this approach.

A different angle on the same problem is breadth-first search: amounts are nodes, each coin is an edge, and the fewest coins is the shortest path from 0 to amount. Same O(amount × coins) worst case; it can stop early when the answer is small.

Edge cases

• amount = 0 — dp[0] = 0 is returned with no loop work.
• Unreachable amount — [5] and 3: every entry stays infinity, so the function returns −1. [2] and 3 also returns −1, even though smaller amounts like 2 are reachable.
• Coins bigger than the amount — c <= a skips them.
• Returning inf — convert to −1 before returning; int(inf) raises an error.

Follow-ups

• How many combinations make the amount (Coin Change II)? — count instead of minimise: ways[0] = 1, and ways[a] += ways[a - c]. Put coins on the outer loop so each mix is counted once: [1, 3, 4] and 6 gives 4 (1×6, 1×3 + 3, 3 + 3, 1×2 + 4).
• How many orderings? — put the amount on the outer loop instead, and 1 + 1 + 4 and 4 + 1 + 1 count separately: the same input gives 9. The loop order is the difference between the two questions.
• Which coins? — keep, for each amount, the coin that gave the minimum; then walk back from amount subtracting that coin.