Partition Equal Subset Sum

Difficulty: Hard

Problem

Given an array of positive integers, decide whether it can be split into TWO subsets with EQUAL sums. [1,5,11,5] can — [1,5,5] and [11] both sum to 11. [1,2,3,5] cannot: no way to balance the two sides. 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 = [1,5,11,5]
Output: true
Explanation: Split into [1,5,5] and [11] — both subsets sum to 11, so the partition exists.

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

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

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