Coin Change

Problem

You are given a list of coins of distinct denominations and an integer amount. You have an unlimited supply of each coin. Return the fewest number of coins whose values sum to exactly amount. If no combination sums to amount, return -1.

Examples

• coins = [1, 2, 5], amount = 11 → 3 — 5 + 5 + 1.
• coins = [2], amount = 3 → -1 — odd target, only even coins.
• coins = [1, 2, 5], amount = 0 → 0 — zero coins make zero.

Constraints

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

amount up to 10^4 and few coin types means an O(amount × len(coins)) DP is the intended fit. Greedy “take the biggest coin first” is wrong in general (e.g. coins = [1, 3, 4], amount = 6: greedy takes 4+1+1 = 3 coins, but 3+3 = 2 is optimal).

Think about it first

TL;DR

Bottom-up DP over amounts 0 … amount, each = 1 + min(dp[a - coin]) — O(amount × #coins) time, O(amount) space.

The recurrence

Let dp[a] be the fewest coins summing to exactly a. The last coin placed is some denomination c <= a, leaving subproblem a - c:

dp[a] = min over coins c with c <= a of ( dp[a - c] + 1 )
dp[0] = 0
dp[a] = +infinity   if no coin yields a reachable a   (report as -1)

Approach 1 — Brute-force recursion

Try every coin as the “last” one and recurse.

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        def fewest(a: int) -> float:
            if a == 0:
                return 0
            if a < 0:
                return float("inf")
            return min((fewest(a - c) + 1 for c in coins), default=float("inf"))
        result = fewest(amount)
        return result if result != float("inf") else -1

Complexity: exponential — roughly O(#coins ^ amount) time, O(amount) stack.

Why the constraints kill it: with amount = 10^4 and several coins, the recursion tree explodes because each amount is recomputed through countless different coin orders.

Approach 2 — Top-down memoization

The insight: there are only amount + 1 distinct subproblems, fewest(0) … fewest(amount); cache each.

from functools import cache

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        @cache
        def fewest(a: int) -> float:
            if a == 0:
                return 0
            if a < 0:
                return float("inf")
            return min((fewest(a - c) + 1 for c in coins), default=float("inf"))
        result = fewest(amount)
        return result if result != float("inf") else -1

Complexity: O(amount × #coins) time, O(amount) space (cache + stack).

Approach 3 — Bottom-up tabulation

The insight: solve every amount from 0 up to amount in order, so each dp[a - c] is already final. Use amount + 1 as a sentinel “infinity” (no valid answer can exceed amount coins).

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        INF = amount + 1
        dp = [0] + [INF] * amount
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a and dp[a - c] + 1 < dp[a]:
                    dp[a] = dp[a - c] + 1
        return dp[amount] if dp[amount] != INF else -1

Walkthrough (coins = [1, 2, 5], amount = 11), a few key cells:

• dp[1] = dp[0]+1 = 1
• dp[2] = min(dp[1]+1, dp[0]+1) = 1
• dp[5] = min(dp[4]+1, dp[3]+1, dp[0]+1) = 1
• dp[6] = min(dp[5]+1, dp[4]+1, dp[1]+1) = 2 (5 + 1)
• dp[10] = dp[5]+1 = 2 (5 + 5)
• dp[11] = min(dp[10]+1, dp[9]+1, dp[6]+1) = 3 (5 + 5 + 1)

Return 3. ✓

Complexity: O(amount × #coins) time, O(amount) space. The space is inherent — unlike the fixed-window recurrences, dp[a] can depend on dp[a - c] for a coin c up to amount away, so the table cannot collapse to a constant number of scalars.

Approach 4 — BFS over amounts (well-known alternative)

The insight: picture a graph where node a connects to a - c for each coin. The fewest coins is the shortest path from amount to 0, and breadth-first search — exploring level by level — finds shortest paths in an unweighted graph. Each BFS “level” adds one coin, so the first time we reach 0 gives the minimum count.

from collections import deque

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        if amount == 0:
            return 0
        seen = {amount}
        queue = deque([amount])
        depth = 0
        while queue:
            depth += 1
            for _ in range(len(queue)):
                a = queue.popleft()
                for c in coins:
                    nxt = a - c
                    if nxt == 0:
                        return depth
                    if nxt > 0 and nxt not in seen:
                        seen.add(nxt)
                        queue.append(nxt)
        return -1

Walkthrough (coins = [1,2,5], amount = 11): level 1 reaches {10, 9, 6}; level 2 reaches {5, 4, 1, 8, 7, 3, …}; level 3 subtracts a coin from 5, 4, or 1 to hit 0 → returns depth 3. ✓ Because BFS never revisits an amount (seen), it often prunes work versus the full table, though worst-case complexity matches.

Complexity: O(amount × #coins) time, O(amount) space.

Common pitfalls

• Greedy denomination picking. Taking the largest coin that fits is wrong for arbitrary denominations ([1,3,4], amount=6). DP is required.
• amount = 0. The answer is 0, not -1; make sure the base case handles it before any coin loop.
• Sentinel arithmetic. If you use float("inf"), comparisons are fine; if you use an integer sentinel, use amount + 1 (any real answer is <= amount) and check against it exactly.
• Skipping the c <= a guard (tabulation) or the a < 0 guard (recursion) — subtracting a too-large coin must not count as a valid path.

Pattern takeaway

Coin Change is the archetypal unbounded-knapsack / min-over-choices 1-D DP: the state is the remaining amount, and each step you take the best over all first (or last) choices. Two hallmarks distinguish it from the fixed-window recurrences (Fibonacci, House Robber): the transition takes a min (or count) over many predecessors, and those predecessors can be far back — so the table stays O(amount) and does not shrink to rolling scalars.