p61 — Partition Equal Subset Sum

Source: LeetCode 416 · Medium · Topics: 0/1 Knapsack DP, Bitmask Companies (2024–2025): Amazon (high), Microsoft (high), Google (medium-high), Meta (medium) Loop position: The 0/1 knapsack archetype — subset-sum reduction with a target. Tests recognizing knapsack disguised as a partition problem and the bitmask optimization that turns O(n·S) into O(n·S/w) with a single Python int.

1. Quick Context

Given an array of positive integers, can it be partitioned into two subsets with equal sum?

Reduction: Let total = sum(nums). If total is odd, return False. Else, ask: is there a subset summing to total / 2? That’s subset-sum, solvable by 0/1 knapsack.

dp[s] = True if some subset sums to s
init dp = {0: True}
for x in nums:
    for s from target down to x:   # reverse to avoid reusing x
        dp[s] |= dp[s - x]
return dp[target]

O(n·S) time, O(S) space where S = total/2. Bitmask optimization: store dp as a Python int and dp |= dp << x.

2. LeetCode Link + Attempt Gate

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

STOP. 20-min timer.

3. Prerequisite Concepts

• 0/1 knapsack DP.
• Why the inner loop iterates backwards in 1D-space knapsack.
• Pythonic bigint bit-shift.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Equal-sum 2-partition existence.

2. Clarify: Positives only? (Yes on LC 416, 1 ≤ nums[i] ≤ 100, length ≤ 200.) Empty array? Edge case.

3. Examples: [1,5,11,5] → True ([1,5,5] vs [11]); [1,2,3,5] → False.

5. Brute force: Try all 2ⁿ subsets and check sum. Exponential.

6. Target: O(n·S) DP where S = total/2.

7. Pattern: 0/1 knapsack on sum.

8. Develop: see solution.py.

9. Test: odd total; single element; two equal; LC examples; all equal.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 The reduction

Two-way partition with equal sums means each part sums to total / 2. If total is odd, no partition exists. Else the question becomes: does some subset sum to total / 2? — classic subset-sum, NP-hard in general but pseudo-polynomial (O(n·S)) when sums are bounded.

LC 416 constraints: n ≤ 200, nums[i] ≤ 100 → S ≤ 100·200 / 2 = 10000. O(n·S) ≈ 2M ops. Fine.

6.2 Why the inner loop runs backwards in 1D-space knapsack

dp[s] after iteration represents “subset-sum reachable using items considered so far, sum = s.” Adding item x:

for s from target down to x:
    dp[s] = dp[s] OR dp[s - x]

Iterating backwards ensures dp[s - x] reflects the previous iteration (item x not used yet). Iterating forward would let you use x multiple times — which is the unbounded knapsack (coin change pattern), not 0/1.

This is the single most common bug in 1D knapsack code.

6.3 The bitmask trick — O(n·S/w)

dp is a bitset of length target+1 where bit s = “sum s reachable.” Adding item x corresponds to:

dp |= dp << x

A single bigint OR-shift handles all sums in parallel, processed w ≈ 64 bits per machine word. Final check: (dp >> target) & 1.

Python’s bigints make this a one-liner. CPython internally handles arbitrary-precision shifts efficiently. For S=10000, this is ~157 words per << — vastly faster than the explicit DP loop.

This trick is famous in competitive programming (cf. Codeforces “knapsack with bitmask”).

6.4 Optional optimization: early termination by total halving

Sort nums descending. If any item > target, no partition possible. Track partial sums; if max-remaining + current < target, prune. For LC 416’s constraints, plain DP is fine — but for stress/contest sizes, these prunes matter.

6.5 Reconstructing the subset

Standard knapsack: maintain a back-pointer table choose[i][s] ∈ {0, 1} indicating whether item i was taken to reach dp[i][s]. Walk back from (n, target). O(n·S) memory.

6.6 Connection to NP-hardness

General subset-sum is NP-complete (Karp’s 21). The DP we just wrote is “pseudo-polynomial” — polynomial in the numeric value of S, not in its bit-length. If S is exponential in n, the DP blows up. LC 416 caps S to keep this practical.

For huge S, approximation algorithms exist (Fully Polynomial Time Approximation Scheme — FPTAS by Ibarra-Kim, 1975) with O(n³/ε) for a (1-ε)-approximation.

6.7 Generalizations

• LC 494 Target Sum: assign ± to each number to reach target sum. Reduces to subset-sum: subset of “+” items has sum (total + target) / 2.
• LC 698 Partition to K Equal Subsets: k-way partition. NP-hard; backtracking with pruning, since k > 2.
• LC 474 Ones and Zeroes: 2D knapsack (two constraints).
• LC 1049 Last Stone Weight II: minimize partition-sum difference; same DP, return total - 2·max_reachable.

7. Anti-Pattern Analysis

1. Forget to check total % 2 — if odd, immediately False; otherwise wasted compute.
2. Inner loop iterates forward — turns 0/1 into unbounded knapsack, gives wrong answers (allows reusing one element multiple times).
3. Forget dp[0] = True — empty subset sums to 0; without it the recurrence yields all False.
4. 2D dp[n+1][S+1] when 1D works — wastes memory; also masks the forward-vs-backward bug because 2D doesn’t have it.
5. Use int(total / 2) instead of total // 2 — floating-point coercion; on huge totals can produce wrong target.
6. Bitmask version: dp |= dp << x without setting dp |= 1 initially — empty subset isn’t represented.

8. Skills & Takeaways

• Recognize 0/1 knapsack in disguise (partition, target sum, last-stone).
• Master forward-vs-backward inner loop discipline.
• Python bigint bitmask trick for ~64× speedup.
• Pseudo-polynomial vs polynomial distinction.

9. When to Move On

• Solve LC 416 cold in 12 min.
• Solve LC 494 (Target Sum) in 8 min as a reduction to LC 416.
• Solve LC 1049 (Last Stone Weight II) in 8 min.
• Implement the bitmask version in 3 lines.
• Explain backward-loop necessity in 30 seconds.

10. Company Context

• Amazon: L6 onsite; productized as “can these orders be split evenly across two warehouses?”
• Microsoft: L65+; LC 494 follow-up.
• Google: L5; bitmask variant scores Senior signal.
• Meta: E5; LC 698 multi-way partition as Hard follow-up.

Scorecard for strong: “Recognized knapsack reduction; correct backward inner loop; mentioned bitmask trick; solved LC 494 and LC 1049 as variants; noted pseudo-polynomial complexity.”

11. Interviewer’s Lens

12. Level Delta

• Mid (L4): Correct 1D-space DP, backward inner loop, returns dp[target].
• Senior (L5): + bitmask int version + reconstructs the subset + LC 494 instant.
• Staff (L6): + pseudo-polynomial vs NP-hardness framing + LC 698 (k-way) backtracking + FPTAS awareness.
• Principal (L7+): + Karp’s reduction from 3-SAT + dynamic-programming-over-bitmasks for k-partition + production scheduling (multiway number partitioning, LPT/Karmarkar-Karp heuristics).

13. Follow-up Q&A

Q1: LC 494 Target Sum (assign ± to reach target). A1: Let P = sum of “+” items, N = sum of “-” items. P - N = target, P + N = total → P = (total + target) / 2. Subset-sum to P. (Check (total + target) is non-negative and even.)

Q2: LC 1049 Last Stone Weight II (minimize |sumA - sumB|). A2: Same DP up to target = total // 2. Answer = total - 2 · max(s for s ≤ target if dp[s]).

Q3: Reconstruct one valid subset, not just existence. A3: Keep 2D dp[i][s] and back-pointers; walk back from (n, target) to recover which items were chosen.

Q4: K-way equal partition (LC 698). A4: NP-hard. Use backtracking with bucket-fill: sort descending, try placing each item in one of k buckets, prune when a bucket exceeds target or when two empty buckets occur at the same recursion frame (symmetry break). Bitmask DP dp[mask] = True if items in mask can be partitioned into completed buckets works for n ≤ ~16.

Q5: How does the bitmask dp |= dp << x work? A5: dp is a bigint where bit s = “sum s reachable.” Shifting left by x shifts every reachable sum by +x (adding item x). ORing with original = “reachable without x” ∪ “reachable with x.” All sums updated in one CPU-friendly bigint op.

14. Solution Walkthrough

See solution.py:

• can_partition_dp — 1D-space 0/1 knapsack, backward inner loop.
• can_partition_bitmask — Python bigint bitmask, three-line core.
• can_partition_brute — try all 2ⁿ subsets (stress only).

15. Beyond the Problem

Principal code review: “Subset-sum looks like a toy problem until you realize it sits at the root of scheduling theory. The ‘two-machine make-span minimization’ problem in operations research is exactly LC 1049 — and Karmarkar-Karp’s 1982 differencing heuristic, which is the practical state of the art for multiway number partitioning, exists because exact DP doesn’t scale beyond ~10⁴ items. When you write dp |= dp << x in Python, you’re using a trick that lets bitset-based knapsack solve problems with sums in the millions in a few hundred milliseconds — a technique pulled straight from competitive programming and bioinformatics (peptide-mass matching). The interview asks ‘can it be partitioned’ — production asks ‘how unbalanced is the best partition, what’s the minimum make-span, can we approximate within ε in real time.’ Learn the spectrum from pseudo-poly DP to FPTAS to heuristics.”