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)

Each amount depends on one predecessor per coin. For coins = [1, 2, 5]:

flowchart LR
  P5["dp[a-5]"] -->|"+1"| A["dp[a] = min"]
  P2["dp[a-2]"] -->|"+1"| A
  P1["dp[a-1]"] -->|"+1"| A

Approach 1 — Brute-force recursion

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

def coinChange(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 it fails at these constraints: with amount = 10^4 and several coins, the recursion tree grows exponentially because each amount is recomputed through many different coin orders.

Approach 2 — Top-down memoization

There are only amount + 1 distinct subproblems, fewest(0) … fewest(amount). Cache each one.

from functools import cache

def coinChange(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

Solve every amount from 0 up to amount in order, so each dp[a - c] is already final when needed. Use amount + 1 as a sentinel for infinity (no valid answer can exceed amount coins).

def coinChange(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)

Model 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 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

def coinChange(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, returning 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.