vault

Coin Change

20 min read

Coin Change

The Coin Change family covers two distinct dynamic-programming problems on a multiset of coin denominations and a target amount: (a) the minimum-coins variant — find the fewest coins (with unlimited supply per denomination) that sum to the target, returning -1 if impossible (LeetCode 322); and (b) the count-the-ways variant — count the number of distinct combinations of coins that sum to the target (LeetCode 518). Both are unbounded-knapsack-flavored DPs over a 1D state dp[amount], but the iteration order differs sharply between them, and the count variant has a famous trap that double-counts permutations as distinct combinations if the loops are nested in the wrong order. This note treats both side by side and contrasts them with the greedy approach (which fails in general, despite working on US currency).

1. Intuition — The Cashier’s Drawer

You are the cashier in a shop. A customer is owed $0.41 in change, and your drawer holds an unlimited supply of pennies (1¢), nickels (5¢), dimes (10¢), and quarters (25¢). Two natural questions arise:

  • (a) Minimum coins. What is the smallest number of coins that sums to 41¢? Most cashiers’ instinct is greedy: take the biggest coin that fits, repeat. With US denominations: 25 + 10 + 5 + 1 = 41 → 4 coins. That happens to be optimal here. But this is a coincidence of US coinage; we will see in §10.1 that for arbitrary denominations the greedy approach can produce suboptimal answers, and that is precisely why we need DP.
  • (b) Number of ways. In how many distinct combinations can you assemble 41¢? Some examples: 41 pennies; 1 nickel + 36 pennies; 1 dime + 31 pennies; 1 quarter + 16 pennies; 1 quarter + 1 nickel + 11 pennies; etc. We do not care about the order in which the coins are stacked (using a quarter then a dime is the same combination as a dime then a quarter); we only care about the multiset of coins used.

These two questions have different aggregations (a min vs a sum), different base cases (∞ vs 1), and — crucially — different iteration orders in their tabulation. They are siblings, not the same problem, and the differences are pedagogically important.

The change-making problem in its general form (with arbitrary denominations) was studied by J. W. Wright in 1975 (“The change-making problem,” Journal of the ACM) and shown to be NP-hard in the size of the binary encoding of the amount — but the standard O(amount · |coins|) DP is pseudo-polynomial and runs comfortably for interview-sized inputs. This is the same pseudo-polynomial nature as 01 Knapsack and Subset Sum.

2. Tiny Worked Example

Let coins = [1, 2, 5] and amount = 11 for both variants.

2.1 Variant A — Minimum Coins

State: dp[a] = minimum number of coins summing to amount a. Recurrence: dp[a] = 1 + min over c in coins, c ≤ a of dp[a - c]. Base: dp[0] = 0 (zero coins make zero); dp[a] = +∞ for unreached amounts.

We iterate a = 0, 1, 2, ..., 11 and for each a try every coin c ≤ a. The table fills as follows (∞ shown as - for readability):

a01234567891011
init0-----------
a=101----------
a=2011---------
a=30112--------
a=401122-------
a=5011221------
a=60112212-----
a=701122122----
a=8011221223---
a=90112212233--
a=1001122122332-
a=11011221223323

Sample derivations: dp[3] = min(dp[3-1]+1, dp[3-2]+1) = min(1+1, 1+1) = 2. dp[5] = min(dp[4]+1, dp[3]+1, dp[0]+1) = min(3, 3, 1) = 1. dp[11] = min(dp[10]+1, dp[9]+1, dp[6]+1) = min(3, 4, 3) = 3 — achievable via 5+5+1 or 5+2+2+2 (the latter uses 4 coins, not 3, so the minimum is from 5+5+1).

Answer: dp[11] = 3.

2.2 Variant B — Number of Ways (Combinations)

State: dp[a] = number of distinct combinations summing to a. Recurrence (correct version): loop over coins outermost, for each coin c loop a = c..amount and add dp[a] += dp[a - c]. Base: dp[0] = 1 (one way to make 0: the empty multiset), dp[a > 0] = 0 initially.

We iterate coins in the order 1, 2, 5. After processing coin 1, the table represents “number of ways using only coin 1” — one way per amount (use that many pennies):

a01234567891011
init100000000000
after coin 1111111111111
after coin 2112233445566
after coin 511223456781011

After processing coin 2 (running a = 2..11 and adding dp[a-2] to dp[a]), we now count combinations using coins from {1, 2}. For instance, dp[4] = 3: those are 1+1+1+1, 1+1+2, 2+2. After processing coin 5, the final row counts combinations using {1, 2, 5}.

Answer: dp[11] = 11. (Spot-check: combinations include 1×11, 1×9 + 2×1, 1×7 + 2×2, 1×5 + 2×3, 1×3 + 2×4, 1×1 + 2×5, 5 + 1×6, 5 + 1×4 + 2×1, 5 + 1×2 + 2×2, 5 + 2×3, 5 + 5 + 1 — that’s 11.)

2.3 The Wrong Iteration Order — Permutations Instead of Combinations

If you instead loop a outermost and coins innermost (mirroring variant A’s loop structure), you count permutations: 1+2 and 2+1 become distinct, vastly inflating the count. We will return to this in the pitfalls (§11.2).

3. Pseudocode

Variant A — Minimum coins:

dp[0] = 0
for a in 1..amount:
    dp[a] = +∞
    for each coin 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] < +∞ else -1

Variant B — Number of combinations:

dp[0] = 1
for a in 1..amount:
    dp[a] = 0
for each coin c in coins:                 # OUTER loop is coins
    for a in c..amount:                   # INNER loop is amount, ASCENDING
        dp[a] += dp[a - c]
return dp[amount]

The pseudocode mirrors the table fills from §2. Note the critical asymmetry: A puts amount outside, coins inside; B puts coins outside, amount inside. A’s order does not double-count because the min aggregation is order-insensitive; B’s order is the entire mechanism that prevents double-counting.

4. Python Implementation

4.1 Variant A — Minimum Coins

Top-down (memoization):

from functools import lru_cache
 
def coinChange_topdown(coins: list[int], amount: int) -> int:
    @lru_cache(maxsize=None)
    def dp(a: int) -> int:
        if a == 0:
            return 0
        if a < 0:
            return float('inf')
        return min(dp(a - c) for c in coins) + 1
    result = dp(amount)
    return result if result < float('inf') else -1

The function recurses over remaining amount a. The base case a == 0 returns 0 (zero coins needed); a < 0 is an unreachable / over-shoot signal that returns +∞ so that the enclosing min ignores that branch. The +1 accounts for the coin we just “spent.” The @lru_cache decorator (Python functools standard library) memoizes on a, which has at most amount + 1 distinct values — bounding the work to O(amount · |coins|).

Bottom-up (tabulation):

def coinChange_bottomup(coins: list[int], amount: int) -> int:
    INF = amount + 1                       # sentinel larger than any valid answer
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] <= amount else -1

We use the sentinel INF = amount + 1 rather than float('inf') because any valid answer is at most amount (worst case is amount 1-cent coins), so this sentinel is comfortably larger than any reachable value while staying as a Python int (faster comparisons than floats). The final check dp[amount] <= amount distinguishes “computed a real value” from “still at sentinel.” Time is O(amount · |coins|), space is O(amount).

4.2 Variant B — Number of Combinations

Top-down (memoization), with explicit “next-coin” index to avoid double-counting:

from functools import lru_cache
 
def coinChange2_topdown(amount: int, coins: list[int]) -> int:
    coins = sorted(coins)                  # canonical order for combinations
    @lru_cache(maxsize=None)
    def dp(remaining: int, i: int) -> int:
        # Number of combinations using coins[i:] summing to `remaining`.
        if remaining == 0:
            return 1
        if i == len(coins) or remaining < 0:
            return 0
        # Choice: use coin i (and stay on coin i, allowing re-use), or skip to coin i+1.
        return dp(remaining - coins[i], i) + dp(remaining, i + 1)
    return dp(amount, 0)

Here the second argument i enforces a canonical order on combinations: we either keep using the current coin coins[i] (unbounded re-use) or advance to coins[i+1], but we never go back. This eliminates the 1 + 2 vs 2 + 1 duplication at the source — the recursion only ever generates combinations in non-decreasing coin-index order. State space is O(amount · |coins|); per-state work is O(1).

Bottom-up (tabulation) — the canonical form:

def coinChange2_bottomup(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:                        # OUTER: each coin processed once
        for a in range(c, amount + 1):     # INNER: amounts in ASCENDING order
            dp[a] += dp[a - c]
    return dp[amount]

The loop ordering is the entire correctness argument: by fixing a coin c and sweeping all amounts before moving to the next coin, we ensure each combination (multiset of coins) is generated exactly once. After processing the first k coins, dp[a] equals the number of combinations of coins[0..k-1] summing to a. Re-entering the outer loop with the next coin extends each existing combination by zero or more copies of the new coin. Time O(amount · |coins|), space O(amount).

5. Complexity

For both variants, with n = |coins| and W = amount:

  • Time: O(n · W). Derivation: the state space is O(W) (one cell per amount in 1D), and per state we do O(n) work (in variant A, take a min over n coins; in variant B, the outer loop multiplies the inner sweep). Equivalently from the “states × work” formula in DP State Identification.
  • Space: O(W) for the 1D table. Constant-factor memory savings are possible (e.g., if all coin denominations are small, you can use a 2D dp[i][a] with O(n · W) space and recover combinations more easily, but the 1D form is what is expected).
  • Pseudo-polynomial caveat. Same as 01 Knapsack: O(n · W) is polynomial in the value of W, not in the number of bits to encode W. If W = 10^18, this DP is infeasible regardless of how small n is. Practical interview values of W ≤ 10^4 (LeetCode 322’s stated bound) make this irrelevant, but the formal complexity classification is weakly NP-hard — established via reduction from subset-sum, with Lueker (1975) and Wright (1975) as the foundational references (the Wikipedia Change-making problem entry traces the chain).
  • Beyond the textbook DP. Chan and He (SOSA 2020, paper) gave a deterministic O(W · log W · log log W) algorithm and a randomized O(W · log W) for the single-target variant — sub-quadratic in W when n is large — by formulating the recurrence as a sequence-convolution problem. This is well past the interview bar but worth knowing exists: the O(n · W) DP is not the asymptotic ceiling.

6. Variant A — Minimum Coins, Path Reconstruction

If you need not just the count but the actual coins used, store a parent[a] array recording which coin was last used to reach a:

def coinChange_with_path(coins: list[int], amount: int) -> tuple[int, list[int]]:
    INF = amount + 1
    dp = [INF] * (amount + 1)
    parent = [-1] * (amount + 1)
    dp[0] = 0
    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
                parent[a] = c
    if dp[amount] > amount:
        return -1, []
    # Reconstruct.
    path = []
    a = amount
    while a > 0:
        path.append(parent[a])
        a -= parent[a]
    return dp[amount], path

parent[a] stores the coin used in the optimal transition to a. We backtrack from a = amount until a = 0. This is the general witness-reconstruction template for 1D DPs.

7. Variant B — Permutations Instead of Combinations

If the problem actually asks for permutations (1+2 and 2+1 count as distinct sequences — sometimes called “staircase” or “compositions”), swap the loop order:

def numberOfPermutations(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1
    for a in range(1, amount + 1):         # OUTER: amount
        for c in coins:                    # INNER: coins
            if c <= a:
                dp[a] += dp[a - c]
    return dp[amount]

This is LeetCode 377 (“Combination Sum IV” — confusingly named: despite “combination” in the title, it counts permutations). The loop swap is the entire algorithmic difference. Both are correct DPs; they answer different questions.

8. Equivalence to Unbounded Knapsack

Coin Change variant A is unbounded knapsack with all values equal to 1, minimizing items: each “item” (coin) has weight c and value 1, the knapsack capacity is amount, and we want the minimum total value such that total weight equals amount exactly (rather than the maximum value subject to weight ≤ capacity). Variant B is counting subsets-with-repetition that sum to a target — a sibling of Partition Equal Subset Sum but with repetition allowed.

This unification is useful: any technique you learn for Unbounded Knapsack (rolling-array space, item-by-item processing for combinations) transfers directly. See also the Subset Sum family for the bounded variants.

9. Diagram — How the Two Loop Orders Generate Different Sets

flowchart TD
    subgraph CombLoop[Outer coins, inner amount — combinations]
        C1[Process coin 1<br/>extends every existing<br/>combination by some 1s] --> C2[Process coin 2<br/>extends each combination<br/>from C1 by some 2s] --> C3[Process coin 5<br/>extends each combination<br/>from C2 by some 5s]
    end
    subgraph PermLoop[Outer amount, inner coins — permutations]
        P1[At amount a:<br/>add dp from a−1 via coin 1] --> P2[Then add dp from a−2 via coin 2] --> P3[Then add dp from a−5 via coin 5]
        P3 --> P4[Each amount visited once,<br/>but coin orderings produce<br/>distinct sequences]
    end

What this diagram shows. The two loop orders implement two different generation processes. The combinations order (top) processes one coin at a time, treating each coin as adding a layer on top of the table built from previous coins; a combination is uniquely associated with the sequence of coins as iterated, so no duplicates arise. The permutations order (bottom) at each amount a considers every coin as a possible “last” coin, which means a sequence ending in 1 then a sequence ending in 2 for the same multiset both get counted. The arrows in the top loop show that combinations are built incrementally over coins; the arrows in the bottom show that permutations are built incrementally over amounts. This visual is the single best mnemonic for which loop goes outside.

10. Greedy Approach — Why It Fails in General

10.1 The US-Coinage Coincidence

For US denominations [1, 5, 10, 25] (and many real-world currencies), the greedy “take the largest coin that fits” approach is optimal. This is not a general property of the change-making problem; it is a specific structural property of these denomination sets. Pearson’s 2005 paper (“A polynomial-time algorithm for the change-making problem,” Operations Research Letters) gives an O(n³) algorithm to test whether a denomination set is “canonical” (i.e., greedy-optimal). For arbitrary denominations, greedy can be arbitrarily bad.

10.2 The Classic Counterexample

Coins [1, 3, 4], target 6. Greedy takes 4 + 1 + 1 = 6 (3 coins). Optimal: 3 + 3 = 6 (2 coins). Greedy committed to the largest coin (4) and was then stuck taking two 1s; it could not “reconsider” its choice. DP enumerates both possibilities and picks correctly.

It is worth emphasizing that no simple closed-form characterization of canonical denomination sets is known. Pearson (2005) gave an O(n³) test by reducing the search for a minimum counterexample to O(n²) candidate amounts — a polynomial-time decision procedure, not a structural theorem (per the published paper). Kozen and Zaks (1994) had earlier given an algorithm polynomial in the largest denomination but not in the input size, leaving the genuinely-polynomial question open until Pearson resolved it. Structural classifications are known only for small fixed-size systems: 2-coin and 3-coin systems have explicit characterizations, 4-coin and 5-coin systems have been classified by case analysis, and 6-coin canonical systems were characterized only as recently as Cai et al. (arXiv:2111.12392). For arbitrary n, the rule remains “run Pearson’s test, do not guess.”

10.3 Lesson

Greedy is O(amount / smallest_coin) and very fast when correct. DP is O(amount · |coins|) and always correct. In an interview, always default to DP for coin-change problems unless the problem explicitly fixes the denomination set to a known-canonical one. Mentioning that greedy works on US coinage but not arbitrary coinage is a good way to demonstrate awareness of the trade-off. For the deeper theory of why greedy works on certain structured inputs — exchange arguments, the matroid framework, and the “stays ahead” technique — see Greedy Algorithms — Proof Techniques; the change-making problem is the canonical motivating example where the natural greedy strategy is not provably optimal, which is precisely how that note frames the bound.

11. Pitfalls

11.1 Returning 0 Instead of -1 for Unreachable Amount (Variant A)

If dp[amount] is still +∞ after the table fills, the amount is unreachable with the given coins — return -1 (LeetCode’s convention). A common bug returns 0 because the sentinel was forgotten. Test on coins = [2], amount = 3 → must return -1.

11.2 Wrong Loop Order for Combinations (Variant B)

This is the single most-tested DP pitfall in interviews. The combinations variant requires coins-outer / amount-inner. Reversed, it counts permutations and inflates the answer. Memorize the rule: for combinations, the coin loop is outer. If you can articulate why (each combination is generated once because we never “go back” to a previous coin), you’ve internalized the recurrence.

11.3 Wrong Base Case dp[0] (Variant B)

dp[0] = 1 means “there is one way to make 0: the empty multiset.” Setting dp[0] = 0 causes the entire table to be 0 (every recurrence ultimately bottoms out at dp[0], and 0 propagates). This is a textbook off-by-one base-case error and is silent — the code runs and returns 0 for everything.

11.4 Iterating a from 0 Instead of c in the Inner Loop (Variant B)

The inner loop must start at a = c, because for a < c you cannot use coin c. Iterating from a = 0 and writing if c <= a: dp[a] += dp[a - c] is correct but slightly wasteful; the cleaner form is for a in range(c, amount + 1). This is a style nit, not a correctness issue, but interview reviewers notice.

11.5 Using float('inf') as Sentinel (Variant A)

float('inf') works but introduces floating-point comparisons in a hot loop, slower than integer comparisons. The idiom INF = amount + 1 exploits the fact that any valid answer is at most amount (use that many 1-cent coins) — so amount + 1 is a strict upper bound on any reachable dp[a]. After the fill, dp[amount] > amount cleanly detects unreachability.

11.6 Confusing “Amount” with “Number of Coins”

dp[a] indexes by amount (an integer in cents/dollars), not by coin count. Easy slip when typing dp[len(coins)] or dp[amount + len(coins)]. The state is amount, period.

11.7 Top-Down with Mutable List in Cache Key

If you parametrize the recursion by a list of remaining coins (e.g., for a “use each coin at most once” twist), lru_cache will fail because lists are unhashable. Convert to tuple, or — better — parametrize by an index into the sorted coin list rather than carrying the list itself. The index is a single integer, and the cache key shrinks accordingly.

11.8 Greedy Trap

If the interviewer presents the problem with US-like denominations, your gut may say “greedy works.” Fight the gut. Even if greedy passes the sample test cases, it is wrong for arbitrary denominations and the interviewer may add a hidden test case ([1, 3, 4], target 6) to expose it. Always write the DP.

11.9 Coins with Value 0

Some pathological inputs include coin = 0. Variant A would loop forever (dp[a] = 1 + dp[a - 0] = 1 + dp[a]); variant B would infinite-loop similarly. Sanitize input: filter out non-positive coins or assert on entry.

11.10 Negative Amount Handling

Recursive variant A might be called with negative a if you forget the c <= a guard. The base case a < 0 → +∞ (in the top-down version) catches this; the bottom-up form prevents it via the if c <= a check.

12. Diagram — The Decision Tree for Variant A on coins=[1,2,5], amount=5

flowchart TD
    A5[dp 5 = ?] --> S1[via coin 1: dp 4 + 1]
    A5 --> S2[via coin 2: dp 3 + 1]
    A5 --> S5[via coin 5: dp 0 + 1 = 1]
    S1 --> A4[dp 4 = 2]
    S2 --> A3[dp 3 = 2]
    S5 --> A0[dp 0 = 0 base]
    A5 --> R[dp 5 = min 3, 3, 1 = 1]

What this diagram shows. The recurrence at amount 5 evaluates three transitions — one per coin denomination ≤ 5 — and aggregates with min. The via coin 5 branch reaches the base case dp[0] = 0 in a single hop and contributes 1, beating the two-coin branches. The arrows are dependency arrows (dp[5] depends on dp[4], dp[3], dp[0]). A correct iteration order computes dp[0], dp[3], dp[4] before dp[5]. In the table fill, this is automatic because we sweep a = 0, 1, 2, ..., 11 in order. The diagram also visualizes why the recurrence is O(|coins|) per state: one outgoing edge per coin denomination.

13. Common Interview Problems

ProblemLeetCode #Variant
Coin ChangeLC 322Minimum coins (variant A)
Coin Change IILC 518Number of combinations (variant B)
Combination Sum IVLC 377Number of permutations (loop swap of B)
Perfect SquaresLC 279Min “coins” where coins = perfect squares ≤ n
Minimum Cost For TicketsLC 983DP with day-budget decisions; coin-like
Number of Dice Rolls With Target SumLC 1155Bounded version (each coin used ≤ k times)
Word BreakLC 139Same loop structure as variant A but boolean
Combination SumLC 39Backtracking (enumerates combinations explicitly) — useful contrast

14. Open Questions

  • Is there a closed-form (rather than algorithmic) characterization of canonical denomination sets for arbitrary n? Closed-form rules are known for 2-, 3-, 4-, 5-, and (per Cai et al. 2021) 6-coin systems by case analysis, but no uniform rule for general n is known — Pearson’s O(n³) test remains the best general tool.
  • For the bounded case (each coin at most k_i times), the DP becomes 2D dp[i][a] and the rolling-array trick requires more care. When is the bounded case sub-quadratic?
  • Are there approximation algorithms (FPTAS — Fully Polynomial-Time Approximation Scheme) for change-making? Subset-sum has one (Ibarra & Kim 1975); change-making’s status is similar.
  • When the amount is astronomically large (10^18) but |coins| is tiny, does the problem admit a number-theoretic shortcut (e.g., via the Frobenius number / Chicken McNugget theorem)?

15. See Also

Graph View

Backlinks