Partition Equal Subset Sum (LeetCode 416)
You're given an integer array nums. Decide whether it can be split into two subsets whose element sums equal each other -- return true if such a split exists and false otherwise.
Worked Examples
nums = [1,5,11,5]truenums = [1,2,3,5]false⚖️Formal Constraints & Bounds
1 <= nums.length <= 2001 <= nums[i] <= 100
Core Insight
Backward iteration in 1D array enforces 0/1 knapsack single-use constraints in O(N · Sum) time.
Real-World Scenario & Production Applications
Load balancing server tasks between two identical cores, equal dual-partition asset distribution.
Subproblems & Recurrence Decomposition3 Phases
If the total array sum is odd, equal partition is impossible (return False). Otherwise, reduce the problem to 0/1 Knapsack: find a subset summing exactly to target = total_sum // 2.
if total_sum % 2 != 0:
return False
target = total_sum // 2Step-by-Step Execution Trace Table
| Number | Target | Achievable Sums Updated | Result |
|---|---|---|---|
| 1 | 11 | dp[1] = True | - |
| 5 | 11 | dp[6], dp[5] = True | - |
| 11 | 11 | dp[11] = True | True |
| 1 | total = sum(nums) |
| 2 | if total % 2 != 0: |
| 3 | return False |
| 4 | target = total // 2 |
| 5 | dp = [False] * (target + 1) |
| 6 | dp[0] = True |
| 7 | for x in nums: |
| 8 | for w in range(target, x - 1, -1): |
| 9 | dp[w] = dp[w] or dp[w - x] |
| 10 | return dp[target] |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Partitioning an array into two equal-sum subsets requires finding a subset summing to exactly $\sum nums / 2$. This is a 0/1 Knapsack decision problem: each number can be used at most once. In a space-optimized 1D boolean array, iterating the target capacity *backwards* from $target$ down to $x$ guarantees that no element is counted multiple times in the same step, solving the problem in $O(N \times target)$ pseudopolynomial time. 🔄 The Analogy: Filling Out a Form You Can Only Read Top-to-Bottom Once
Imagine a checklist of achievable sums, and you're updating it one number at a time: "can I now hit sum s, using this number plus something I already knew was achievable?" If you scan the checklist forward (low sums to high), you risk reading an entry you just updated in this same pass — meaning the same number could be counted in the same sum calculation twice, as if you had two copies of it. Scanning backward (high sums to low) guarantees you only ever read entries that reflect the checklist before this number was considered at all — so each number can only ever be counted once.
🔑 The Key Idea in the Code
Reversing the inner loop is the entire difference between "0/1" (each item used at most once) and "unbounded" (items reusable) — the exact same array-update trick, just read in the opposite direction.
Odd total sum cannot be partitioned: If
sum(nums) % 2 != 0, dividing into two equal integer subsets is mathematically impossible; returnFalseimmediately.Updating 1D DP table in forward direction: Iterating the inner target loop forward (
for j in range(num, target + 1):) allows the same number to be used multiple times (unbounded knapsack). Iterate backwards fromtargetdown tonum.Target sum calculation: The target subset sum is
total // 2. Searching fortotalor forgettingtarget = sum(nums) // 2tests the wrong property.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Splitting an array into two subsets with equal aggregate properties.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: dp[s] is True if subset sum s is achievable using a subset of processed items.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
for w in range(target, x - 1, -1), counting down: thendp[w - x]has not been touched by thisxyet, so each number is used at most once. Counting up lets one number count twice ([1]would reach 2).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Knapsack DP. The array splits into two subsets with equal sums exactly when some subset reaches half of the total, so if the total is odd, I return false at once. Otherwise the target is half the total, and I keep one boolean per sum from 0 to the target: dp of w is true when some of the numbers seen so far add up to w. For each number x, I walk w from the target down to x and set dp of w to true if dp of w minus x is already true. Going down means the smaller sum I read has not used x yet, so each number counts at most once. The trap is the loop direction: going up lets one number be added twice, so the array [1] would wrongly reach a sum of 2. That's O(N times target) time and O(target) space."
Complexity & Mathematical Proof
O(N · Target)
Look at the execution steps: Target = sum(nums) // 2. 1D boolean array of size Target + 1 is updated backwards from Target down to num for each of the N numbers. Total N * Target operations.
O(Target) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. 1D boolean array of size Target + 1.
T(N, S) = N · (S / 2) = O(N · Target)
Derivation Progression
Target = ∑ nums / 2
Odd sum returns False immediately.
for j from Target down to v: dp[j] ∨= dp[j - v]
Each number updates at most Target + 1 cells, each in O(1).
O(N · Target)
Pseudo-polynomial time.
Variable Definitions
Total number of elements in the array
Half of the total array sum (sum(nums) // 2)
Memory Architecture & Bounds
O(1) Iterative
O(Target) 1D boolean table
O(1) Boolean return
Boundary Best / Worst Cases
when the total is odd: one pass to sum, then return.
.
on even sum.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "partition array into two subsets with equal sum". 0/1 Knapsack Boolean Subset Sum: partitioning into equal halves requires finding a subset that sums exactly to .
. Time budget: operations (ms).
Scale: at the limits (200 numbers, each at most 100) the target is at most , so the table is booleans and about updates. In Python the same reachable-sums set fits in one integer used as a bitset (bits |= bits << x), which does each number's update in one shift.
Partition Equal Subset Sum (LeetCode 416)
You're given an integer array nums. Decide whether it can be split into two subsets whose element sums equal each other -- return true if such a split exists and false otherwise.
Worked Examples
nums = [1,5,11,5]truenums = [1,2,3,5]false⚖️Formal Constraints & Bounds
1 <= nums.length <= 2001 <= nums[i] <= 100
Core Insight
Backward iteration in 1D array enforces 0/1 knapsack single-use constraints in O(N · Sum) time.
Real-World Scenario & Production Applications
Load balancing server tasks between two identical cores, equal dual-partition asset distribution.
Subproblems & Recurrence Decomposition3 Phases
If the total array sum is odd, equal partition is impossible (return False). Otherwise, reduce the problem to 0/1 Knapsack: find a subset summing exactly to target = total_sum // 2.
if total_sum % 2 != 0:
return False
target = total_sum // 2Step-by-Step Execution Trace Table
| Number | Target | Achievable Sums Updated | Result |
|---|---|---|---|
| 1 | 11 | dp[1] = True | - |
| 5 | 11 | dp[6], dp[5] = True | - |
| 11 | 11 | dp[11] = True | True |
| 1 | total = sum(nums) |
| 2 | if total % 2 != 0: |
| 3 | return False |
| 4 | target = total // 2 |
| 5 | dp = [False] * (target + 1) |
| 6 | dp[0] = True |
| 7 | for x in nums: |
| 8 | for w in range(target, x - 1, -1): |
| 9 | dp[w] = dp[w] or dp[w - x] |
| 10 | return dp[target] |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Partitioning an array into two equal-sum subsets requires finding a subset summing to exactly $\sum nums / 2$. This is a 0/1 Knapsack decision problem: each number can be used at most once. In a space-optimized 1D boolean array, iterating the target capacity *backwards* from $target$ down to $x$ guarantees that no element is counted multiple times in the same step, solving the problem in $O(N \times target)$ pseudopolynomial time. 🔄 The Analogy: Filling Out a Form You Can Only Read Top-to-Bottom Once
Imagine a checklist of achievable sums, and you're updating it one number at a time: "can I now hit sum s, using this number plus something I already knew was achievable?" If you scan the checklist forward (low sums to high), you risk reading an entry you just updated in this same pass — meaning the same number could be counted in the same sum calculation twice, as if you had two copies of it. Scanning backward (high sums to low) guarantees you only ever read entries that reflect the checklist before this number was considered at all — so each number can only ever be counted once.
🔑 The Key Idea in the Code
Reversing the inner loop is the entire difference between "0/1" (each item used at most once) and "unbounded" (items reusable) — the exact same array-update trick, just read in the opposite direction.
Odd total sum cannot be partitioned: If
sum(nums) % 2 != 0, dividing into two equal integer subsets is mathematically impossible; returnFalseimmediately.Updating 1D DP table in forward direction: Iterating the inner target loop forward (
for j in range(num, target + 1):) allows the same number to be used multiple times (unbounded knapsack). Iterate backwards fromtargetdown tonum.Target sum calculation: The target subset sum is
total // 2. Searching fortotalor forgettingtarget = sum(nums) // 2tests the wrong property.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Splitting an array into two subsets with equal aggregate properties.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: dp[s] is True if subset sum s is achievable using a subset of processed items.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
for w in range(target, x - 1, -1), counting down: thendp[w - x]has not been touched by thisxyet, so each number is used at most once. Counting up lets one number count twice ([1]would reach 2).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Knapsack DP. The array splits into two subsets with equal sums exactly when some subset reaches half of the total, so if the total is odd, I return false at once. Otherwise the target is half the total, and I keep one boolean per sum from 0 to the target: dp of w is true when some of the numbers seen so far add up to w. For each number x, I walk w from the target down to x and set dp of w to true if dp of w minus x is already true. Going down means the smaller sum I read has not used x yet, so each number counts at most once. The trap is the loop direction: going up lets one number be added twice, so the array [1] would wrongly reach a sum of 2. That's O(N times target) time and O(target) space."
Complexity & Mathematical Proof
O(N · Target)
Look at the execution steps: Target = sum(nums) // 2. 1D boolean array of size Target + 1 is updated backwards from Target down to num for each of the N numbers. Total N * Target operations.
O(Target) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. 1D boolean array of size Target + 1.
T(N, S) = N · (S / 2) = O(N · Target)
Derivation Progression
Target = ∑ nums / 2
Odd sum returns False immediately.
for j from Target down to v: dp[j] ∨= dp[j - v]
Each number updates at most Target + 1 cells, each in O(1).
O(N · Target)
Pseudo-polynomial time.
Variable Definitions
Total number of elements in the array
Half of the total array sum (sum(nums) // 2)
Memory Architecture & Bounds
O(1) Iterative
O(Target) 1D boolean table
O(1) Boolean return
Boundary Best / Worst Cases
when the total is odd: one pass to sum, then return.
.
on even sum.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "partition array into two subsets with equal sum". 0/1 Knapsack Boolean Subset Sum: partitioning into equal halves requires finding a subset that sums exactly to .
. Time budget: operations (ms).
Scale: at the limits (200 numbers, each at most 100) the target is at most , so the table is booleans and about updates. In Python the same reachable-sums set fits in one integer used as a bitset (bits |= bits << x), which does each number's update in one shift.