Saturday, September 5, 2026

🔬 Saturday Deep Dive: 背包问题两大模式 — Coin Change & Partition Equal Subset Sum (17 min read)

📊 NeetCode: 99/150 · SysDesign: 60/40✅ · Behavioral: 60/40✅ · Frontend: 37/50 · AI: 30/30✅

🔥 Day 127 — Expert Phase!

Overview / 概述

今天我们深入两种最重要的背包 DP 模式：无限背包（Unbounded Knapsack） 和 0/1 背包。

这两个模式用一条规则就能区分：内层循环的方向。

• 无限背包：内层 for amount 从小到大（可以重复用同一物品）
• 0/1 背包：内层 for j 从大到小（每个物品只用一次）

Two of the most critical DP patterns, separated by a single rule: the direction of the inner loop.

• Unbounded knapsack: inner loop goes left → right (items are reusable)
• 0/1 knapsack: inner loop goes right → left (each item used at most once)

Master this and you unlock a whole family of interview problems cold.

Part 1: Theory / 理论基础 (5 min)

1.1 动态规划的本质 / The Essence of DP

DP 解决两类问题：

1. 计数：有多少种方法（Number of Ways）
2. 最优化：最小 / 最大值（Min / Max optimization）

硬币找零属于最优化；分割等和子集属于可行性判断。两者都用背包框架。

Both coin change and subset sum fit the knapsack framework. Coin change is optimization; partition is feasibility.

三要素 / Three Pillars:

1.2 两个模板 / Two Knapsack Templates

Template A — Unbounded Knapsack（完全背包）

每种物品可用无数次（硬币、台阶）。

dp = [float('inf')] * (target + 1)
dp[0] = 0

for coin in coins:
    for i in range(coin, target + 1):   # ← left to right: allows reuse
        dp[i] = min(dp[i], dp[i - coin] + 1)

Template B — 0/1 Knapsack（01背包）

每个物品最多用一次（每个数字只属于一个分区）。

dp = [False] * (target + 1)
dp[0] = True

for num in nums:
    for j in range(target, num - 1, -1):  # ← right to left: prevents reuse
        dp[j] = dp[j] or dp[j - num]

🔑 The Single Rule That Separates Them:

为什么方向很重要？/ Why direction matters:

Left → right: when processing dp[i], dp[i - coin] was already updated in this same pass, meaning the coin can be "used again."

Right → left: when processing dp[j], dp[j - num] still holds its value from before this item was processed, so the item is never counted twice.

Part 2: Step-by-Step Implementation / 一步一步实现 (8 min)

Problem 1: Coin Change (#322) — Unbounded Knapsack

🔗 LeetCode: https://leetcode.com/problems/coin-change/

📹 NeetCode: https://www.youtube.com/watch?v=H9bfqozjoqs

Problem: Given coin denominations and a target amount, return the minimum number of coins to make the amount. Return -1 if impossible.

Input: coins = [1, 5, 6, 9], amount = 11

Expected: 2 (5 + 6 = 11)

#### Naive Approach: Recursion — O(coins^amount), TLE

def coinChange_naive(coins, amount):
    def dfs(remaining):
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        # Try every coin, pick the one giving the minimum
        return 1 + min(dfs(remaining - c) for c in coins)

    result = dfs(amount)
    return result if result != float('inf') else -1

Exponential — re-computes overlapping subproblems. Add memoization → O(amount × coins). Bottom-up is cleaner.

def coinChange(coins: list[int], amount: int) -> int:
    # dp[i] = minimum coins needed to make amount i
    # Initialize to inf (impossible) except dp[0]=0 (base case: 0 coins for 0)
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        # Left to right: we can use this coin multiple times
        for i in range(coin, amount + 1):
            # Option: use this coin + solve for (i - coin)
            dp[i] = min(dp[i], 1 + dp[i - coin])

    return dp[amount] if dp[amount] != float('inf') else -1

#### 🔍 Trace-Through with coins = [1, 5, 6, 9], amount = 11

Code trace matches expected output. ✅

Problem 2: Partition Equal Subset Sum (#416) — 0/1 Knapsack

🔗 LeetCode: https://leetcode.com/problems/partition-equal-subset-sum/

📹 NeetCode: https://www.youtube.com/watch?v=IsvocB5BJhw

Problem: Can you partition the array into two subsets with equal sum?

Key Insight: Total must be even → find a subset summing to total // 2.

Input: nums = [1, 5, 11, 5]

Expected: True (subsets: [1, 5, 5]=11, [11]=11)

#### Why 0/1 Knapsack?

def canPartition(nums: list[int]) -> bool:
    total = sum(nums)

    # If total is odd, impossible to split evenly
    if total % 2 != 0:
        return False

    target = total // 2

    # dp[j] = True if we can form sum j using elements seen so far
    dp = [False] * (target + 1)
    dp[0] = True  # Base case: empty subset sums to 0

    for num in nums:
        # CRITICAL: right to left — prevents using num more than once
        for j in range(target, num - 1, -1):
            # Can we form sum j?
            # Without num: dp[j] stays as is
            # With num:    need dp[j - num] to already be True
            dp[j] = dp[j] or dp[j - num]

        # Optional: early exit if target already reachable
        if dp[target]:
            return True

    return dp[target]

#### 🔍 What Breaks If You Go Left → Right?

# BUG: left-to-right iteration for 0/1 knapsack
nums = [3]
target = 6

# dp = [T, F, F, F, F, F, F]  (only dp[0]=True)

# Left to right with num=3:
# j=3: dp[3] = dp[3] or dp[0] = True   ← used num=3 once (correct so far)
# j=6: dp[6] = dp[6] or dp[3] = True   ← used num=3 AGAIN (BUG!)
# Returns True — but [3] cannot sum to 6!

# Right to left with num=3 (correct):
# j=6: dp[6] = dp[6] or dp[3] = False or False = False
# j=3: dp[3] = dp[3] or dp[0] = False or True  = True
# Returns False ✅

Bonus: Coin Change II (#518) — Counting with Unbounded Knapsack

🔗 https://leetcode.com/problems/coin-change-ii/

def change(amount: int, coins: list[int]) -> int:
    # dp[i] = number of distinct ways to make amount i
    dp = [0] * (amount + 1)
    dp[0] = 1  # One way to make 0: use no coins

    # Outer = coins, inner = amount (left to right)
    # This prevents counting [1,2] and [2,1] as distinct (combinations, not permutations)
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

Why coins in outer loop? If you put amount in the outer loop (like Coin Change #322), each coin is "reconsidered" at every amount independently — which counts permutations. Putting coins in outer loop ensures coin 1 is fully "committed" before coin 2 is ever considered.

Cheat Sheet: Three Problems, Three Variants

Part 3: Edge Cases & Gotchas / 边界情况 (2 min)

Coin Change

coinChange([], 5)          # → -1  (no coins, impossible)
coinChange([1, 2, 3], 0)   # → 0   (base case: 0 coins for amount 0)
coinChange([5], 3)          # → -1  (coin larger than amount)
coinChange([2], 3)          # → -1  (odd amount, only even coin)

Float('inf') vs large sentinel: Use float('inf') not amount + 1 — cleaner comparisons; amount + 1 can cause off-by-one bugs when amount is 0.

Partition Equal Subset Sum

canPartition([1, 2, 3, 5])   # sum=11, odd → False immediately
canPartition([10, 10])        # sum=20, target=10 → True
canPartition([100])           # sum=100, target=50 → False (single element)
canPartition([1, 1])          # sum=2, target=1 → True

# Large input: nums can have 200 elements, values up to 100
# target up to 200*100/2 = 10000 → dp array size O(10000), fine

Comparison Table

Part 4: Real-World Application / 实际应用 (2 min)

支付系统 / Payment Systems

Coin Change maps directly to ATM dispensing: given bill denominations, find the minimum number of bills to dispense $X. Stripe's internal settlement engine uses similar DP to minimize transaction splits.

资源调度 / Resource Scheduling

0/1 Knapsack appears in:

• Cloud bin packing: Can these microservices fit in this instance (memory = knapsack capacity, services = items)?
• A/B test balancing: Partition users into two cohorts of equal aggregate spend.
• Kubernetes scheduling: Pack pods into nodes without exceeding CPU/memory limits.

Bitset 加速 / Bitset Optimization

For large-scale partition problems (sums up to 10^5), production systems use Python's arbitrary-precision integers as bitsets — 64× faster than a bool array:

def canPartition_bitset(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2

    # dp as bitmask: bit i is set if sum i is reachable
    dp = 1  # bit 0 set: sum 0 reachable with empty subset
    for num in nums:
        dp |= (dp << num)  # shift = "add num to all currently reachable sums"

    return bool(dp & (1 << target))
# Time: O(n × target / 64) — 64x speedup on CPython

Sometimes asked as an optimization follow-up at FAANG+.

Part 5: Interview Simulation / 面试模拟 (3 min)

Q1: You solved Coin Change. Now each coin can only be used once. How does your solution change?

Change the inner loop from left→right to right→left. The dp array and transition formula stay identical. This one-line change converts unbounded knapsack to 0/1 knapsack with no change to time or space complexity.

Q2: What's the time and space complexity of Coin Change? Can space be reduced?

Time: O(amount × |coins|). Space: O(amount) for the 1D dp array — already optimal. You can't go below O(amount) because you need all subproblem answers simultaneously.

Q3: Why does Coin Change II put coins in the outer loop instead of amount?

If amount is outer, each coin is reconsidered at every amount independently, which counts permutations (e.g., [1,2] and [2,1] counted separately). With coins outer, coin 1 is fully "committed" before coin 2 is introduced, counting combinations only.

Q4: Can you solve Partition Equal Subset Sum with memoization (top-down)?

from functools import lru_cache

def canPartition_memo(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2

    @lru_cache(maxsize=None)
    def dp(i: int, remaining: int) -> bool:
        if remaining == 0:
            return True
        if remaining < 0 or i == len(nums):
            return False
        # Include nums[i] or skip it
        return dp(i + 1, remaining - nums[i]) or dp(i + 1, remaining)

    return dp(0, target)
# O(n × target) time and space — same as bottom-up

Q5: When do you prefer top-down vs bottom-up?

Top-down (memoization) is often easier to write and only computes the states you actually need. Bottom-up (tabulation) has no recursion overhead, better cache locality, and avoids stack overflow for large inputs. In interviews, top-down is faster to code and explain; in production, bottom-up is usually preferred.

Summary / 总结

🔗 Practice List:

• https://leetcode.com/problems/coin-change/
• https://leetcode.com/problems/coin-change-ii/
• https://leetcode.com/problems/partition-equal-subset-sum/
• https://leetcode.com/problems/target-sum/
• https://leetcode.com/problems/last-stone-weight-ii/
• https://leetcode.com/problems/ones-and-zeroes/