Partition Equal Subset Sum

1. Problem & Core Objective

Given an array of positive integers, return true if it can be split into two subsets with equal sum.

nums = [1,5,11,5]   →  true      [1,5,5] and [11], both sum to 11
nums = [1,2,3,5]    →  false     total 11 is odd

Constraints: 1 <= nums.length <= 200 · 1 <= nums[i] <= 100

What's actually being tested: reframing a partition question as a subset-sum question — if one subset sums to total/2, the rest necessarily does too. Then it's 0/1 knapsack, and the descending loop that makes it 0/1 rather than unbounded is the technical crux.

2. First-Principles Thought Process

The reframe

Two subsets with equal sums means each sums to total / 2. And crucially, finding one such subset is enough — the complement automatically has the same sum.

So the question collapses to: is there a subset summing to exactly total / 2?

That's subset sum, a classic 0/1 knapsack.

The O(1) rejection

If total is odd, no split is possible — you can't halve an odd integer into two equal integers.

if (total % 2 != 0) return false;

That's an immediate rejection before any DP, and it handles [1,2,3,5] in constant time.

The boolean DP

dp[s] = "can some subset sum to exactly s?"

For each number n, every previously reachable sum s makes s + n reachable too:

dp[s] = dp[s] || dp[s − n]

Base case dp[0] = true — the empty subset sums to zero.

The descending loop — the crux

for (int n : nums)
    for (int s = target; s >= n; s--)        // DESCENDING
        dp[s] |= dp[s - n];

Why descending? Because each number may be used at most once.

Ascending, dp[s - n] might already have been updated in this same pass — meaning n was already used to reach s - n, and using it again to reach s uses it twice. That's unbounded knapsack, which is Coin Change.

Descending, dp[s - n] still holds the value from before n was considered, so n contributes at most once.

Ascending versus descending is the entire difference between unbounded and 0/1 knapsack, and it's the same read-the-previous-generation discipline as Bellman-Ford's clone.

Complexity

O(n × total/2) = 200 × 10,000 = 2 × 10^6. That's pseudo-polynomial — linear in the value of the target, not in its number of digits. Worth naming, because subset-sum is NP-complete and this doesn't contradict that.

3. Solution Paths

Approach 1 — Try every subset (brute force)

public boolean canPartition(int[] nums) {
    int total = 0;
    for (int n : nums) total += n;
    if (total % 2 != 0) return false;
    return subsetSum(nums, 0, total / 2);
}

private boolean subsetSum(int[] nums, int i, int remaining) {
    if (remaining == 0) return true;
    if (i == nums.length || remaining < 0) return false;
    return subsetSum(nums, i + 1, remaining - nums[i])     // take
        || subsetSum(nums, i + 1, remaining);              // skip
}

• Time O(2^n) · Space O(n) stack

Counter-questions on this approach

⭐ "Why exponential?"

Take-or-skip at every element, so 2^n subsets. At n = 200 that's 1.6 × 10^60 — beyond any conceivable computation.

But the distinct states are only (i, remaining) pairs — 200 × 10,000 = 2 × 10^6. That gap is the DP signal.

⭐ "Why i + 1 in both branches?"

Because each element is used at most once. Passing i in the take branch would allow reuse, turning it into unbounded knapsack — a different problem.

That's the recursive form of the same 0/1-versus-unbounded distinction that the loop direction expresses in the tabulated version.

"Does the remaining < 0 check matter given all values are positive?"

It prunes branches that have overshot. With all-positive values, overshooting is unrecoverable, so it's a valid cut — the same reasoning as Combination Sum's sorted break.

With negative values present it would be invalid, and the problem would be much harder.

Approach 2 — 2-D DP

public boolean canPartition(int[] nums) {
    int total = 0;
    for (int n : nums) total += n;
    if (total % 2 != 0) return false;
    int target = total / 2;

    boolean[][] dp = new boolean[nums.length + 1][target + 1];
    for (int i = 0; i <= nums.length; i++) dp[i][0] = true;   // empty subset sums to 0

    for (int i = 1; i <= nums.length; i++)
        for (int s = 1; s <= target; s++) {
            dp[i][s] = dp[i - 1][s];                           // skip nums[i-1]
            if (s >= nums[i - 1]) dp[i][s] |= dp[i - 1][s - nums[i - 1]];   // take it
        }

    return dp[nums.length][target];
}

• Time O(n × target) · Space O(n × target)

Counter-questions on this approach

⭐ "Why does the take branch read row i−1 rather than row i?"

Because taking nums[i-1] means it's now used, so the remainder must be formed from the previous items only. Reading row i would allow the same item to contribute twice.

That's the 0/1 constraint made explicit by the row index — and it's exactly what the descending loop enforces implicitly in the 1-D version.

⭐ "Why is dp[i][0] = true for every i?"

The empty subset sums to zero regardless of how many items are available. Every take-chain bottoms out there.

"How much space is that?"

201 × 10,001 booleans ≈ 2 MB. Acceptable, but the 1-D version is 10 KB — and since each row only reads the one above it, the second dimension is unnecessary.

Approach 3 — 1-D DP with a descending loop (optimal)

public boolean canPartition(int[] nums) {
    int total = 0;
    for (int n : nums) total += n;
    if (total % 2 != 0) return false;                  // odd total — impossible

    int target = total / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;                                       // empty subset sums to 0

    for (int n : nums) {
        for (int s = target; s >= n; s--)               // DESCENDING — each n used once
            dp[s] |= dp[s - n];
        if (dp[target]) return true;                    // early exit
    }
    return dp[target];
}

Trace — nums = [1,5,11,5], total = 22, target = 11:

Answer true ✓ — the subset {11} sums to 11, so {1,5,5} does too.

• Time O(n × target) = 2 × 10^6 · Space O(target)

Counter-questions on this approach

⭐ "Why must the inner loop descend?"

Because each number may be used at most once.

Ascending, by the time s is reached, dp[s - n] may already have been set during this same pass — meaning n was used to reach s - n, and using it again for s uses it twice.

Concretely with nums = [3] and target = 6: ascending, dp[3] becomes true, and then at s = 6, dp[6] |= dp[3] is true — claiming 6 is reachable from a single 3. Descending, s = 6 is visited first and reads dp[3] while it's still false, so 6 correctly stays unreachable.

Ascending gives unbounded knapsack (Coin Change), descending gives 0/1. That loop direction is the whole distinction.

⭐ "Why does finding one subset summing to total/2 prove a partition exists?"

Because the complement is forced. If subset A sums to total/2, then the rest sums to total − total/2 = total/2 as well.

So there's no need to construct both halves — the existence of one determines the other. That's the reframe that turns a partition question into a subset-sum question.

⭐ "Why is the odd-total check necessary rather than just an optimisation?"

It's both. total / 2 uses integer division, so an odd total would silently truncate — on [1,2,3,5] with total 11 it would target 5, find {5} or {2,3}, and return true when the correct answer is false.

So it's not merely fast-pathing; without it the algorithm is wrong.

"Why s >= n as the loop bound?"

Below n, the index s - n would be negative. Stopping there is both a bounds guard and correct — sums smaller than n can't include n.

"Why the early exit inside the outer loop?"

Once dp[target] is true, more numbers can't make it false. In practice it often stops well before processing everything, though the worst case is unchanged.

"Is this polynomial?"

Pseudo-polynomial — O(n × target) is linear in the value of the target, which is exponential in its bit length. Subset-sum is NP-complete, and this doesn't contradict that: the constraints cap values at 100 and length at 200, so target <= 10,000.

With values up to 10^9 the same algorithm would be infeasible. Worth naming precisely rather than calling it polynomial.

"Could the total overflow?"

200 values at 100 each caps the total at 20,000 — trivially inside int.

Comparison

4. Why the Optimal Wins

Two reductions, and both are the interesting part.

The reframe: "split into two equal halves" becomes "find one subset summing to total/2", because the complement is automatic. That halves the problem before any algorithm runs.

The dimension collapse: the 2-D table's row i reads only row i−1, so a single array suffices — provided the inner loop descends, which is what prevents an item being reused within a pass.

The framing worth keeping:

Equal partition = subset summing to total/2; the complement is free. Then it's 0/1 knapsack, and the inner loop must DESCEND — ascending would let each number be reused, which is unbounded knapsack.

And the correctness check that isn't just an optimisation: an odd total must be rejected, or integer division silently targets the wrong sum.

5. Java Prerequisites

0/1 knapsack, 1-D

for (int n : nums)
    for (int s = target; s >= n; s--)       // DESCENDING = each item once
        dp[s] |= dp[s - n];

Compare with unbounded knapsack (Coin Change), which ascends.

|= on booleans — dp[s] = dp[s] || dp[s-n], written compactly. Note |= does not short-circuit, but with a plain array read that's irrelevant.

Odd-total rejection — required for correctness, not just speed, because total / 2 truncates.

dp[0] = true — the empty subset sums to zero.

6. Interview Communication Guide

Clarifying questions: Must both subsets be non-empty (effectively yes — with positive values, a zero-sum subset can't match a positive one)? Are values positive (yes — it licenses the overshoot pruning)? Must every element be used (yes — it's a partition, so the two subsets cover everything)?

The pitch

"First the reframe. Two subsets with equal sums means each sums to total / 2 — and finding one such subset is enough, because the complement automatically has the same sum. So the question becomes: is there a subset summing to exactly total / 2?

That's subset sum, a 0/1 knapsack.

Before any DP, there's a constant-time rejection: if the total is odd, no equal split exists. And that's a correctness requirement, not just an optimisation — total / 2 truncates, so on [1,2,3,5] with total 11 it would target 5, find {2,3}, and wrongly return true.

The DP is boolean: dp[s] is 'can some subset sum to s?', seeded with dp[0] = true for the empty subset. For each number, every reachable sum s makes s + n reachable.

The technical crux is that the inner loop must descend. Each number may be used at most once, and ascending would let dp[s - n] already reflect this same number — using it twice.

Concretely with a single 3 and target 6: ascending sets dp[3], then at s = 6 reads it and claims 6 is reachable from one 3. Descending visits 6 first, reads dp[3] while still false, and correctly leaves 6 unreachable.

Ascending is unbounded knapsack, descending is 0/1 — that loop direction is the entire distinction, and it's the same read-the-previous-generation idea as Bellman-Ford's array clone.

O(n × target) = 2 × 10^6 here, O(target) space — about 10 KB versus 2 MB for the 2-D table.

One precision point: that's pseudo-polynomial, linear in the target's value rather than its bit length. Subset-sum is NP-complete, and this doesn't contradict it — the constraints just cap the target at 10,000."

Edge cases to volunteer:

Name [1,2,3,5] and [1]. The first is the odd-total case where omitting the check returns a wrong true; the second has total 1, odd, so it's also rejected immediately.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the actual subsets, not just whether they exist."

Keep the 2-D table (or a parent record) and walk back from dp[n][target], noting at each step whether the item was taken. O(n × target) space — the 1-D collapse forfeits reconstruction, the same trade as elsewhere.

⭐ "Split into k equal subsets rather than 2."

LeetCode 698, and genuinely harder. The complement trick no longer applies — knowing one subset doesn't determine the other k−1. It becomes backtracking with pruning, or a bitmask DP over subsets at O(2^n × n).

Worth naming that k = 2 is special precisely because of the complement.

"Minimise the difference between the two subset sums."

LeetCode 1049 (Last Stone Weight II). Same DP, but instead of asking whether dp[target] is true, find the largest reachable s <= total/2 — the answer is total − 2s. A neat generalisation: equal partition is the case where that difference is 0.

"What if values could be up to 10^9?"

O(n × target) becomes infeasible — that's where pseudo-polynomial stops being enough. With small n you'd use meet-in-the-middle at O(2^(n/2)); otherwise it's genuinely NP-hard.

"What if negative values were allowed?"

The overshoot pruning breaks, and the reachable-sum range extends below zero, so the array needs an offset. The DP still works with a shifted index but the state space grows to cover negative sums.

"Count the number of equal partitions."

Change boolean[] to int[] and |= to +=. Then divide by 2, since each partition is counted once from each half. Same structure, counting combiner — and the halving is an easy thing to forget.