Lab 04 — Unbounded Knapsack (Coin Change)

Goal

Solve Coin Change (LC 322 — minimum coins) and Coin Change II (LC 518 — count combinations) with the full four-stage progression. Internalize the left-to-right iteration that makes 1D-collapsed unbounded knapsack correct, and the loop-nesting trick that distinguishes counting combinations from counting permutations. After this lab you can solve any “unlimited supply” knapsack in <10 minutes from cold start.

Background Concepts

Unbounded knapsack: items can be reused any number of times. The 1D-collapsed DP iterates w left-to-right, the opposite of 0/1 knapsack. That single direction-change is the entire mechanical difference. The semantic difference: when we read dp[w - c] in the left-to-right pass, it has already been updated this round to include coin c zero or more times — so this round’s update can stack another c on top, achieving “use c multiple times”.

Coin Change has two flavors. LC 322 asks for the minimum number of coins to reach amount; the recurrence is dp[w] = min(dp[w], dp[w - c] + 1), initialized to +∞ with dp[0] = 0. LC 518 asks for the count of combinations summing to amount; the recurrence is dp[w] += dp[w - c], initialized to dp[0] = 1. The combinations-vs-permutations trap: with coins outer, sums inner, you count combinations (each combination of coins is counted once regardless of order); with sums outer, coins inner, you count permutations (different orderings of the same coins count separately).

Interview Context

Coin Change (LC 322) is a top-15 phone-screen DP problem at every major company. Coin Change II is asked roughly half as often but tests the deeper combinations-vs-permutations distinction. Bombing LC 322 at L4+ is a near-instant rejection. Senior interviewers often follow up with LC 518 specifically to test whether you understand why the loop nesting matters — the hand-wavy candidate is filtered by this question.

Problem Statement

LC 322 (minimum coins): Given coins of distinct denominations and an integer amount, return the fewest number of coins needed to make up amount. Return -1 if unreachable. Each coin denomination has unlimited supply.

LC 518 (count combinations): Given coins and amount, return the number of distinct combinations that sum to amount.

Constraints

  • 1 ≤ coins.length ≤ 12 (LC 322) / 300 (LC 518).
  • 1 ≤ coins[i] ≤ 2^31 − 1.
  • 0 ≤ amount ≤ 10^4 (LC 322) / 5000 (LC 518).
  • LC 518: answer fits in a signed 32-bit integer.

Clarifying Questions

  1. Are coins distinct? (Yes — given.)
  2. Can each coin be used multiple times? (Yes — unlimited supply; this is what makes it unbounded.)
  3. Is amount=0 valid? (Yes; minimum coins = 0; combinations = 1 — the empty combination.)
  4. LC 518: is [1, 2] different from [2, 1]? (No — combinations only, not permutations.)
  5. Coins can exceed amount? (Yes; just unusable for that amount.)

Examples

LC 322:
coins=[1,2,5], amount=11   → 3   (5+5+1)
coins=[2], amount=3        → -1  (unreachable)
coins=[1], amount=0        → 0
coins=[1,2,5], amount=100  → 20  (twenty 5-coins)

LC 518:
coins=[1,2,5], amount=5    → 4   ([5], [2,2,1], [2,1,1,1], [1×5])
coins=[2], amount=3        → 0
coins=[10], amount=10      → 1

Initial Brute Force (LC 322)

At each step, try every coin:

def coinChange_brute(coins, amount):
    def f(remain):
        if remain == 0: return 0
        if remain < 0: return float('inf')
        best = float('inf')
        for c in coins:
            best = min(best, f(remain - c) + 1)
        return best
    ans = f(amount)
    return ans if ans != float('inf') else -1

Brute Force Complexity

Each call branches into len(coins) recursive calls; depth amount / min(coins). Worst case O(K^(amount)) — exponential. At K=12, amount=10^4, completely infeasible.

Optimization Path

There are only amount + 1 distinct values of remain, so memoization gives O(K · amount) time. Tabulation replaces recursion with a loop. The 1D version uses left-to-right iteration so each coin can be reused.

For LC 518 (counting), the order matters: coins outer (combinations) vs sums outer (permutations). The combinations interpretation is what LC 518 wants.

Final Expected Approach

LC 322 (minimum):

dp[w] = min coins to make w. dp[0] = 0; dp[w > 0] = INF.
For each w in 1..amount:
    For each c in coins where c <= w:
        dp[w] = min(dp[w], dp[w - c] + 1)
Answer: dp[amount] if dp[amount] != INF else -1.

LC 518 (count combinations):

dp[w] = number of combinations summing to w. dp[0] = 1; rest 0.
For each c in coins:                           # COINS OUTER
    For each w in c..amount:                   # SUMS INNER, left-to-right
        dp[w] += dp[w - c]
Answer: dp[amount].

Data Structures Used

  • 1D dp[amount+1] integer array.
  • For brute / memo: recursion + lru_cache.

Correctness Argument

LC 322: dp[w] = min coins to reach w, by induction on w. Base: dp[0] = 0. Inductive step: any optimal solution for w ends with some coin c, leaving w - c to be solved optimally — dp[w - c] + 1. Take the minimum over all coins. Unreachable states stay at INF, propagating correctly under min.

LC 518: by the outer-coins loop, after processing coins c_1, ..., c_k, dp[w] counts combinations of those coins summing to w. Inductive step: when we process c_{k+1} with the inner left-to-right loop, the update dp[w] += dp[w - c_{k+1}] adds combinations that use at least one c_{k+1}. Because the inner loop is left-to-right, dp[w - c_{k+1}] already includes solutions using c_{k+1} zero or more times — so this update accounts for using c_{k+1} exactly 1, 2, 3, … times in turn. Each combination is counted exactly once because every combination has a latest coin index, and only the iteration on that coin index counts it. Outer-coins prevents reordering: [1, 2] and [2, 1] are not separately counted.

Complexity

StageTimeSpace
Brute forceO(K^amount)O(amount)
MemoizedO(K · amount)O(amount)
TabulatedO(K · amount)O(amount)
Space-optimized(same as tabulated; already 1D)O(amount)

Implementation Requirements

All four stages for LC 322; tabulated only for LC 518.

# ==== LC 322: Coin Change (minimum coins) ====

# ---- Stage 1: Brute force ----
def coinChange_brute(coins, amount):
    def f(remain):
        if remain == 0: return 0
        if remain < 0: return float('inf')
        return min((f(remain - c) + 1 for c in coins), default=float('inf'))
    ans = f(amount)
    return ans if ans != float('inf') else -1

# ---- Stage 2: Memoized ----
from functools import lru_cache
def coinChange_memo(coins, amount):
    @lru_cache(None)
    def f(remain):
        if remain == 0: return 0
        if remain < 0: return float('inf')
        return min((f(remain - c) + 1 for c in coins), default=float('inf'))
    ans = f(amount)
    return ans if ans != float('inf') else -1

# ---- Stage 3+4: Tabulated 1D (already optimal space) ----
def coinChange(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for w in range(1, amount + 1):                  # SUMS OUTER, COINS INNER for min variant
        for c in coins:
            if c <= w:
                dp[w] = min(dp[w], dp[w - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

# ==== LC 518: Coin Change II (count combinations) ====

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:                                  # COINS OUTER
        for w in range(c, amount + 1):               # SUMS INNER, LEFT-TO-RIGHT
            dp[w] += dp[w - c]
    return dp[amount]

Tests

  • LC 322: coins=[1,2,5], amount=11 → 3.
  • LC 322: coins=[2], amount=3 → -1.
  • LC 322: coins=[1], amount=0 → 0.
  • LC 322: coins=[186, 419, 83, 408], amount=6249 → 20.
  • LC 518: coins=[1,2,5], amount=5 → 4.
  • LC 518: coins=[2], amount=3 → 0.
  • LC 518: coins=[10], amount=10 → 1.
  • LC 518: amount=0 → 1 (empty combination).
  • Compare: For LC 518 with sums-outer (the wrong way), coins=[1,2], amount=3 gives 3 (1+1+1, 1+2, 2+1) instead of 2 (1+1+1, 1+2).

Follow-up Questions

  1. “Reconstruct one valid combination.” → Track which coin produced each dp[w]; backtrack from dp[amount].
  2. “What if coins are large (up to 10^9)?” → Knapsack table doesn’t fit; switch to BFS over reachable amounts (still O(amount × K)) or to coin-set-specific number theory.
  3. “Constraint: at most K coins total.” → Add a dimension: dp[w][k] = min/count using ≤ k coins.
  4. “All combinations summing to exactly amount, not just count.” → Backtracking; output is exponential in worst case.
  5. “What if some coins have limited supply?” → Bounded knapsack; binary-decompose each coin’s count and reduce to 0/1.

Product Extension

Cash-register optimization (which bills/coins to dispense for change), packet-payload composition (combining MTU-aware fragments), and currency-change problems in financial systems — all reduce to coin change variants.

Language/Runtime Follow-ups

  • Python: INF = amount + 1 (since at most amount coins of value 1) avoids float('inf') arithmetic.
  • Java: int[] dp = new int[amount+1]; Arrays.fill(dp, amount+1); dp[0]=0;.
  • Go: pre-fill via loop; no Arrays.fill shortcut.
  • C++: vector<int> dp(amount+1, amount+1); dp[0]=0;.
  • JS/TS: new Array(amount+1).fill(amount+1) then dp[0]=0.

Common Bugs

  1. LC 322: iterating coins outer, sums inner — works for the minimum variant; misleading for those who later try LC 518 with the same nesting and get permutations.
  2. LC 518: iterating sums outer, coins inner — counts permutations ([1,2] and [2,1] separately) instead of combinations.
  3. Forgetting dp[0] = 1 in LC 518 — every count becomes 0.
  4. Using float('inf') + 1 arithmetic in Python — works (inf + 1 == inf), but slower and obscures intent. Prefer INF = amount + 1.
  5. Forgetting the c <= w guard — out-of-bounds index dp[w - c] when w < c.
  6. Off-by-one in range(1, amount + 1) — must reach amount inclusive.

Debugging Strategy

For LC 322 with coins=[1,2,5], amount=11: after the loop, dp = [0,1,1,2,2,1,2,2,3,3,2,3]. Print dp and check dp[11] = 3. For LC 518 with coins=[1,2,5], amount=5: after processing coin 1, dp = [1,1,1,1,1,1]. After coin 2: dp = [1,1,2,2,3,3]. After coin 5: dp = [1,1,2,2,3,4]. Walking through this manually catches loop-nesting bugs.

Mastery Criteria

  • Recognized “unlimited coins” as unbounded knapsack within 60 seconds.
  • Wrote LC 322 brute recursion in <2 minutes.
  • Wrote LC 322 tabulated in <5 minutes.
  • Articulated why unbounded uses left-to-right iteration in <30 seconds.
  • Wrote LC 518 with the correct outer-coins loop in <5 minutes.
  • Articulated why coins-outer counts combinations and sums-outer counts permutations in <60 seconds.
  • Stated O(K · amount) time and O(amount) space.
  • Solved LC 322 unaided in <10 minutes (full progression).
  • Solved LC 518 unaided in <10 minutes.