Lab 03 — 0/1 Knapsack (Partition Equal Subset Sum)

Goal

Solve Partition Equal Subset Sum (LC 416) by reducing it to 0/1 knapsack. Internalize the right-to-left iteration that makes the 1D-collapsed knapsack correct, and articulate why left-to-right iteration would silently turn it into unbounded knapsack. After this lab you should recognize any subset-sum / partition / target-sum / select-with-budget problem as 0/1 knapsack within 90 seconds.

Background Concepts

0/1 knapsack: N items each with weight w_i and value v_i; pick a subset with total weight ≤ W maximizing total value. The 2D DP has state dp[i][w] = max value using first i items with capacity w. The 1D-collapsed version uses dp[w] and iterates w from W down to w_i — the right-to-left iteration is what prevents an item from being reused within the same outer iteration.

Subset sum is 0/1 knapsack with v_i = w_i and a boolean dp instead of integer-valued. Partition equal subset sum reduces to “is there a subset summing to total / 2?”; if total is odd, return false immediately.

Interview Context

Partition Equal Subset Sum is a top-25 Medium DP problem at Amazon and Microsoft. The 0/1 knapsack pattern shows up in disguise constantly: target sum (LC 494), ones and zeroes (LC 474), last stone weight II (LC 1049), tallest billboard (LC 956). Recognizing the reduction is half the battle. The other half is the right-to-left iteration trick — getting that wrong is one of the most common DP bugs across the entire interview corpus.

Problem Statement

Given a non-empty array nums of positive integers, determine whether it can be partitioned into two subsets with equal sums.

Constraints

  • 1 ≤ nums.length ≤ 200
  • 1 ≤ nums[i] ≤ 100

So the maximum total sum is 200 × 100 = 20,000, and the target is at most 10,000. The 2D DP has 200 × 10001 = 2 × 10^6 cells — comfortable.

Clarifying Questions

  1. Are elements positive? (Yes — given.)
  2. Must the partition use all elements? (Yes — that’s what “partition” means.)
  3. Is the empty subset allowed on either side? (Yes if total is 0 — vacuously true. Not the case here since nums[i] ≥ 1.)
  4. Are duplicates allowed? (Yes — they’re treated as separate items.)
  5. Return value: bool (true / false).

Examples

[1, 5, 11, 5]            → true   (1+5+5 == 11)
[1, 2, 3, 5]             → false  (total=11, odd)
[1, 2, 5]                → false  (total=8, target=4, no subset sums to 4)
[2, 2, 1, 1]             → true   (2+1 == 2+1)
[100]                    → false  (total=100, target=50, no subset)

Initial Brute Force

For each element, recurse on “include it” and “skip it”:

def can_partition_brute(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    def f(i, remain):
        if remain == 0: return True
        if i == len(nums) or remain < 0: return False
        return f(i + 1, remain - nums[i]) or f(i + 1, remain)
    return f(0, target)

Brute Force Complexity

O(2^N) time, O(N) stack. At N=200, 2^200 — completely infeasible.

Optimization Path

There are only N × (target + 1) distinct (i, remain) pairs, so memoization gives O(N · target) time and space. Tabulation replaces recursion with a 2D loop. Since dp[i][w] only reads dp[i-1][...], roll to 1D dp[w] — but iterate w right-to-left so that each item is considered at most once per outer iteration.

The right-to-left direction is the defining trick of 0/1 knapsack. If we iterate left-to-right, then dp[w - w_i] may have already been updated to include item i from the current outer iteration; we’d then re-include item i, turning the algorithm into unbounded knapsack.

Final Expected Approach

Reduce to subset sum: target = total / 2 (or return false if total is odd).

dp[w] = True  if some subset sums to exactly w, considering items processed so far.
dp[0] = True (empty subset sums to 0).
For each num x in nums:
    for w in range(target, x - 1, -1):
        dp[w] = dp[w] or dp[w - x]
Answer: dp[target]

Data Structures Used

  • 2D dp[N+1][target+1] boolean array (tabulated).
  • 1D dp[target+1] boolean array (space-optimized).
  • For brute / memo: recursion + lru_cache.

Correctness Argument

Inductive on items processed. dp[w] = True iff some subset of items processed so far sums to w. Base: dp[0] = True (empty subset). Inductive step: when we process item x, the new dp[w] is True iff (a) it was True before (subset not using x sums to w), OR (b) dp[w - x] was True before processing x (subset summing to w - x plus item x). The right-to-left iteration ensures we read the previous dp[w - x], not the in-iteration one. Termination: we want dp[target] after all items are processed.

Complexity

StageTimeSpace
Brute forceO(2^N)O(N)
MemoizedO(N · target)O(N · target)
TabulatedO(N · target)O(N · target)
Space-optimizedO(N · target)O(target)

For LC 416: N≤200, target≤10000, so ~2×10^6 ops — fast.

Implementation Requirements

All four stages.

# ---- Stage 1: Brute force ----
def can_partition_brute(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    def f(i, remain):
        if remain == 0: return True
        if i == len(nums) or remain < 0: return False
        return f(i + 1, remain - nums[i]) or f(i + 1, remain)
    return f(0, target)

# ---- Stage 2: Memoized ----
from functools import lru_cache
def can_partition_memo(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    @lru_cache(None)
    def f(i, remain):
        if remain == 0: return True
        if i == len(nums) or remain < 0: return False
        return f(i + 1, remain - nums[i]) or f(i + 1, remain)
    return f(0, target)

# ---- Stage 3: Tabulated 2D ----
def can_partition_tab(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = True
    for i in range(1, n + 1):
        for w in range(1, target + 1):
            dp[i][w] = dp[i-1][w]
            if w >= nums[i-1]:
                dp[i][w] = dp[i][w] or dp[i-1][w - nums[i-1]]
    return dp[n][target]

# ---- Stage 4: Space-optimized 1D ----
def canPartition(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for w in range(target, x - 1, -1):  # RIGHT-TO-LEFT
            dp[w] = dp[w] or dp[w - x]
    return dp[target]

Tests

  • [1, 5, 11, 5] → True.
  • [1, 2, 3, 5] → False (odd total).
  • [1, 2, 5] → False (no valid subset).
  • [2, 2, 1, 1] → True.
  • [100] → False.
  • [1, 1] → True.
  • N=200, all nums[i]=1 → True (target=100; pick 100 of them).
  • All four implementations should produce identical bool results — randomized comparator on N≤15.

Follow-up Questions

  1. “Return one valid subset, not just yes/no.” → Track parent pointers in the 2D DP; reconstruct by walking backwards through (i, w).
  2. “Partition into K equal subsets.” (LC 698) → 0/1-knapsack-style DP becomes intractable; use bitmask DP or backtracking with pruning.
  3. “Target sum: how many ways to assign +/- to each number to total exactly T?” (LC 494) → Reduce to subset sum: count subsets summing to (total + T) / 2.
  4. “Minimum subset sum difference.” (LC 1049) → Find largest s ≤ total/2 reachable; answer is total - 2s.
  5. “What if nums[i] can be huge (up to 10^9)?” → Knapsack space blows up. Use Karp-style or reduce by GCD; otherwise NP-hard in general.

Product Extension

Resource allocation (split a budget across two teams equally), load balancing (split a workload across two workers), and “is there a subset with this exact total?” appear in billing systems, accounting reconciliation, and cluster-resource schedulers.

Language/Runtime Follow-ups

  • Python: dp = [False] * (target + 1) is fine; the inner loop’s range(target, x - 1, -1) is the canonical right-to-left form.
  • Java: boolean[] dp = new boolean[target + 1]; defaults to false. Use a BitSet for ~64x speedup: dp.or(dp << x) does the entire row-update in O(target / 64).
  • Go: make([]bool, target+1) and a manual reversed loop.
  • C++: vector<bool> is bit-packed; bitset<10001> is faster but fixed-size.
  • JS/TS: new Uint8Array(target + 1) to avoid the false default-equals-undefined trap.

Common Bugs

  1. Iterating w left-to-right in the 1D version — turns 0/1 into unbounded; spurious True answers.
  2. Forgetting the odd-total short circuit — wastes time and may TLE on edge cases.
  3. Using dp[w] = dp[w-x] instead of dp[w] or dp[w-x] — wipes out previously-set True values.
  4. Off-by-one in range(target, x - 1, -1) — should include w == x (since dp[x] = dp[x] or dp[0] = True for any x ≤ target).
  5. Setting dp[0] = True only on the first iteration — must be set once before any item is processed.

Debugging Strategy

For [1, 5, 11, 5]: after processing [1], dp = [T, T, F, F, F, F, F, F, F, F, F, F] (indexes 0..11). After [1, 5]: dp[6] = T (1+5). After [1, 5, 11]: dp[11] = T. Print dp after each item; if dp[target] becomes True earlier than expected, you’re allowing item-reuse (left-to-right bug).

Mastery Criteria

  • Recognized partition-equal-subset as 0/1 knapsack within 90 seconds.
  • Wrote the reduction to subset sum (target = total / 2) before any code.
  • Wrote the brute recursion in <2 minutes.
  • Wrote the 2D tabulated version in <5 minutes.
  • Performed the 1D collapse with right-to-left iteration in <2 minutes.
  • Articulated why left-to-right would be wrong (item reuse → unbounded knapsack) in <30 seconds.
  • Stated O(N · target) time and O(target) space unprompted.
  • Solved LC 416 unaided in <12 minutes (all four stages).
  • Solved LC 494 (Target Sum) in <12 minutes via the reduction.