322. Coin Change (Medium)

Problem

Given coins of various denominations and a target amount, return the fewest number of coins summing to amount (or -1 if impossible). Coins may be used unlimited times.

Example

• coins = [1, 2, 5], amount = 11 → 3 (5 + 5 + 1)
• coins = [2], amount = 3 → -1
• coins = [1], amount = 0 → 0

LeetCode 322 · Link · Medium

Approach 1: Recursive

f(n) = 1 + min(f(n - c) for c in coins if c ≤ n).

def coin_change(coins, amount):
    def f(n):                                      # L1: define recursive helper
        if n == 0:                                 # L2: O(1) base case
            return 0
        if n < 0:                                  # L3: O(1) base case
            return float('inf')
        best = float('inf')                        # L4: O(1)
        for c in coins:                            # L5: loop over |coins| denominations
            best = min(best, 1 + f(n - c))        # L6: O(1) + recurse
        return best
    result = f(amount)                             # L7: kick off recursion
    return -1 if result == float('inf') else result  # L8: O(1)

Where the time goes, line by line

Variables: n = len(coins), A = the target amount.

Line	Per-call cost	Times executed	Contribution
L2, L3 (base cases)	O(1)	once per call	O(1) each
L5 (coin loop)	O(1)	n per call	O(n) per call
L6 (recurse)	O(n) per branch	branches up to n^A	O(n · n^A) ← dominates

Without memoization every sub-problem is recomputed from scratch. The call tree has up to n choices at each of A levels, giving an exponential blowup.

Complexity

• Time: O(n^A), driven by L6. Exponential, unusable.
• Space: O(A) for the recursion stack.

Approach 2: Top-down memoized

from functools import lru_cache

def coin_change(coins, amount):
    @lru_cache(maxsize=None)
    def f(n):                                      # L1: define memoized helper
        if n == 0:                                 # L2: O(1) base case
            return 0
        if n < 0:                                  # L3: O(1) base case
            return float('inf')
        best = float('inf')                        # L4: O(1)
        for c in coins:                            # L5: loop over n denominations
            best = min(best, 1 + f(n - c))        # L6: O(1) + cached sub-call
        return best
    result = f(amount)                             # L7: kick off recursion
    return -1 if result == float('inf') else result  # L8: O(1)

Where the time goes, line by line

Variables: n = len(coins), A = the target amount.

Line	Per-call cost	Times executed	Contribution
L2, L3 (base cases)	O(1)	once per unique n	O(A) total
L5, L6 (coin loop)	O(n) per unique call	A unique values of n	O(n · A) ← dominates
L7 (initial call)	O(1)	1	O(1)

Each value from 0 to A is computed exactly once. The coin loop inside each call is O(n). Cache lookup and store are O(1) amortized.

Complexity

• Time: O(n · A), driven by L5/L6.
• Space: O(A) for the memo table plus O(A) for the call stack.

Approach 3: Bottom-up DP (canonical)

dp[i] = min coins to make i. dp[0] = 0; dp[i] = min(dp[i - c] + 1) over valid coins.

def coin_change(coins, amount):
    INF = amount + 1                               # L1: sentinel larger than any valid answer
    dp = [INF] * (amount + 1)                     # L2: O(A) init
    dp[0] = 0                                      # L3: base case
    for i in range(1, amount + 1):                 # L4: outer loop, A iterations
        for c in coins:                            # L5: inner loop, n iterations
            if c <= i:                             # L6: O(1) guard
                dp[i] = min(dp[i], dp[i - c] + 1) # L7: O(1) recurrence
    return dp[amount] if dp[amount] != INF else -1 # L8: O(1)

Where the time goes, line by line

Variables: n = len(coins), A = the target amount.

Line	Per-call cost	Times executed	Contribution
L2 (init dp)	O(1)	A+1	O(A)
L3 (base case)	O(1)	1	O(1)
L4 (outer loop)	O(1)	A	O(A)
L5, L7 (inner loop + recurrence)	O(1)	A · n	O(A · n) ← dominates
L8 (return)	O(1)	1	O(1)

The double loop at L4/L5 is the whole story. Every (amount, coin) pair is visited exactly once, and L7 is O(1) table lookup plus comparison. No inner recursion, no re-scanning; the DP order guarantees dp[i - c] is already filled when we need it.

Complexity

• Time: O(A · n), driven by L5/L7 (the double loop).
• Space: O(A) for the dp table.

Unbounded vs. 0/1 knapsack

Coin Change is unbounded, each coin can be used infinitely. The outer loop over amounts lets the DP “re-use” a coin naturally. Compare with 0/1 knapsack (problem 416 Partition Equal Subset Sum), where each item is used at most once and loop order matters.

Summary

Approach	Time	Space
Naive recursion	O(n^A)	O(A)
Top-down memo	O(A · n)	O(A)
Bottom-up DP	O(A · n)	O(A)

Template for “min operations to reach target” under free reuse: Coin Change, Perfect Squares, Minimum Cost For Tickets.

Test cases

# Quick smoke tests, paste into a REPL or save as test_322.py and run.
# Uses the canonical implementation (Approach 3: Bottom-up DP).

def coin_change(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

def _run_tests():
    assert coin_change([1, 2, 5], 11) == 3      # 5+5+1, LeetCode example
    assert coin_change([2], 3) == -1             # impossible
    assert coin_change([1], 0) == 0              # zero amount
    assert coin_change([1], 1) == 1              # single coin exact match
    assert coin_change([2, 5, 10, 1], 27) == 4  # 10+10+5+2
    assert coin_change([186, 419, 83, 408], 6249) == 20
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

Related data structures

• Arrays, DP table indexed by amount