Partition Equal Subset Sum

Difficulty: Hard

Problem

Given an array of positive integers, decide whether you can split its elements into two groups whose totals are exactly equal. Each number goes into exactly one group. For instance, [2,2,4] can be split into [4] and [2,2], while [1,2,6] cannot be balanced no matter how you divide it. This is your first 0/1 knapsack: every number may be used at most once, and a single loop direction carries that whole constraint.

Example

Input: nums = [3,3,4,6,2]
Output: true
Explanation: The total is 18, so each group must add up to 9. Put [3,6] in one group and [3,4,2] in the other, and both sides sum to 9.

Brute-force approach

The naive route forks on every number, include it or exclude it, and walks all 2ⁿ subsets. This lesson jumps straight to the insight that collapses them: those subsets can only land on target+1 distinct sums.

Optimal approach

Key insight: Track which sums are buildable. Each number upgrades the set: every reachable s−num makes s reachable. Sweep backwards so a number can't help itself twice.

Rephrase to subset-sum, gate on parity, then run the 0/1 knapsack: one boolean array of reachable sums, each number swept backwards so it counts at most once.

Steps

Parity gate: odd total → return false immediately
Set target = total / 2. The hunt is for ONE subset hitting it
Seed dp[0] = True: the empty subset builds sum 0
For each number, sweep s from target DOWN to num: dp[s] = dp[s] OR dp[s−num]
Return dp[target]

Time complexity: O(n × target) · Space complexity: O(target)

Pseudocode

function canPartition(nums):
    total = sum(nums)
    if total % 2 == ____:
        return False
    target = total / 2
    
    dp = array of size (target + 1), all False
    dp[____] = True
    
    for num in nums:
        for s from ____ down to ____:
            dp[s] = dp[s] ____ dp[s - num]
    
    return dp[target]

Hints

Two equal integer halves always add to an EVEN total. Which remainder makes the split impossible?
Before considering any number at all, which sum can the empty subset already build?
The 0/1 sweep starts at the TOP (the target) and stops where the number still fits (at num itself), backwards!
Feasibility DP: the old truth survives and the new one joins, which boolean word combines them?

Complexity questions

Without DP, what does the include/exclude recursion cost?

O(2ⁿ), every number doubles the search: include it or don't, so n numbers spawn 2ⁿ subsets. Each number forks the search in two. For 40 numbers that's a trillion subsets, yet they can only land on target+1 distinct sums. The table exists precisely so we never walk the subsets one by one.

The table runs in O(n × target). Why the strange label 'pseudo-polynomial'?

target is a VALUE, not a count. Write it with twice as many digits and the work squares. Polynomial in the number's magnitude, exponential in its written size. Complexity is honestly measured against input LENGTH. A 6-digit target means about a million columns from just six characters of input, and doubling the digits squares the magnitude, and the work. Fast when sums are small: that's the real contract.

The 1D array is O(target). How does it relate to the classic 2D knapsack table?

It IS the 2D dp[item][sum] table, space-optimized: each row only reads the row above, and the backwards sweep lets the new row overwrite the old one in place. The textbook version is dp[i][s] over 'the first i numbers'. Row i consults only row i−1, so one array suffices: IF you sweep backwards, reading old values before overwriting them. The direction trick and the space optimization are the same move wearing two hats.

Where does this reachable-sums engine show up next?

'Target Sum' and 'Last Stone Weight II': the same 0/1 subset-sum core, with sign twists layered on top. Target Sum's +/− assignments and Last Stone Weight II's stone-smashing both reduce to 'which subset sums are reachable?'. Rephrase, derive the target, then run this exact backwards-OR loop.

Check your understanding of Partition Equal Subset Sum

'Split the array into two equal-sum halves'. What is this question REALLY asking?

Does SOME subset sum to exactly total/2? Find it, and the leftovers automatically form the other half. You never need to build both subsets. If one subset hits total/2, the numbers you didn't pick sum to total − total/2 = total/2 as well, the split assembles itself. The rephrase turns a vague 'partition' into a concrete target hunt.

Before any DP runs: what's the free disqualifier?

If the TOTAL is odd, return false instantly: two equal integers can't sum to an odd number. If both sides sum to k, the total is 2k, always even. An odd total is impossible before we examine a single subset, so the parity gate runs first and costs one modulo operation.

The state sentence: what does dp[s] mean?

dp[s] is TRUE if some subset of the numbers CONSIDERED SO FAR sums to exactly s, with dp[0] = True from the start, via the empty subset. Say the sentence before writing code: 'can I build sum s from what I've seen so far?' The empty subset builds 0 with zero effort, so dp[0] = True is the seed every later truth grows from.

Why must the inner loop run BACKWARDS, from target down to num?

Forward order would let the SAME number be counted twice in one subset. Dp[s−num] might already include num from this very round. Backwards reads only last round's values. Sweeping high-to-low, dp[s−num] is still the PREVIOUS round's truth: untouched this round, so it can't secretly contain the number we're placing right now. That's the 0/1 'use each number once' guarantee, encoded purely in loop direction.

When a number num arrives, what does it do to the set of reachable sums?

Every already-reachable s−num makes s reachable too: dp[s] = dp[s] OR dp[s−num]. Each number offers one upgrade: every sum you could already build gets a '+num' twin. Old truths survive (the OR keeps dp[s] alive), new ones join. The reachable set only ever grows.