416. Partition Equal Subset Sum

Given an integer array, decide whether it can be split into two subsets with equal sums. The key move: reduce to a classic 0/1 subset-sum — can any subset sum to total / 2? A boolean DP set, updated in reverse order, solves it in O(n · target) time.

● Medium0/1 KnapsackSubset SumDP with SetTypeScript

PROBLEM What we're solving

Given a non-empty array nums of positive integers, return true if it can be partitioned into two subsets with equal sums, false otherwise. For example: nums = [1, 5, 11, 5] → true because [1, 5, 5] sums to 11 and [11] sums to 11. nums = [1, 2, 3, 5] → false.

KEY IDEA Reduce to subset-sum at target = total / 2

Insight → Two subsets with equal sums means each must equal total / 2. So the problem is equivalent to: "does any subset of nums sum to exactly total / 2?" This is the classic 0/1 subset-sum. We never need to find both halves — if one exists, the other is the remainder.

RECIPE Odd-check → set of sums → scan

0 · Odd-sum quick reject. If total is odd, two equal halves are impossible. Return false immediately — saves all work.
1 · Set target. target = total / 2. We only need to check one half.
2 · Initialise dp. Start with dp = new Set([0]). The value 0 is always reachable (pick nothing).
3 · Iterate numbers (snapshot each round). For each num, snapshot the current dp set, then for every s in the snapshot, add s + num if it is ≤ target. Snapshotting (or iterating high→low on a boolean array) prevents using the same number twice.
4 · Early exit. If s + num === target at any point, return true immediately.
5 · Final answer. dp.has(target) after all numbers.

Classic confusion →Forgetting to snapshot (or iterate high-to-low on a boolean array) means a single number can be "used" multiple times in one round — turning 0/1 knapsack into unbounded knapsack. If you see spuriously optimistic results, this is almost always the bug. Snapshot Array.from(dp) before the inner loop, or iterate the boolean array from right to left.

COST Complexity & alternatives

Brute-force recursion

O(2ⁿ)

Try every subset — exponential.

DP set / boolean array

O(n · target)

O(target) space. Usually fast enough for LeetCode constraints.

Space note

Using a boolean[target + 1] array instead of a Set gives the same asymptotic space but better cache performance. Either version is accepted; the Set version is easier to reason about. Both are O(target) — not O(n · target) — for space because we only ever keep one row.

Pattern transfer → This same skeleton solves Target Sum (count subsets summing to a value), Last Stone Weight II (minimize the difference between two partitions), Coin Change (unbounded version — don't snapshot), and the general 0/1 Knapsack. Whenever a prompt asks "can a subset reach value X?", reach for this pattern.

RUN IT Build reachable sums — stop when target is hit

nums =

step 0 / 9

STARTnums = [1, 5, 11, 5]. Sum = 22. Even total. Target = 11. Can we pick a subset summing to it?

1function canPartition(nums: number[]): boolean {
2▶  const total = nums.reduce((a, b) => a + b, 0);
3▶  if (total % 2 !== 0) return false;          // odd sum — impossible
4  const target = total / 2;
5 
6  const dp = new Set<number>([0]);             // reachable subset sums
7 
8  for (const num of nums) {
9    const current = Array.from(dp);           // snapshot before this round
10    for (const s of current) {
11      const ns = s + num;
12      if (ns === target) return true;          // found a valid partition
13      if (ns < target) dp.add(ns);            // only keep sums ≤ target
14    }
15  }
16 
17  return dp.has(target);
18}

State

total

target

—

num

—

current

—

current number (num)snapshot (current)newly added sumtarget reached

slowfast

TYPESCRIPT The solution, annotated

canPartition.ts
function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;          // odd sum — impossible
  const target = total / 2;

  const dp = new Set<number>([0]);             // reachable subset sums

  for (const num of nums) {
    const current = Array.from(dp);           // snapshot before this round
    for (const s of current) {
      const ns = s + num;
      if (ns === target) return true;          // found a valid partition
      if (ns < target) dp.add(ns);            // only keep sums ≤ target
    }
  }

  return dp.has(target);
}

Reading it block by block

Lines 2–3 — odd-sum early exit.If the total is odd we can't split it into two equal integers — bail immediately. This is a free O(1) check that avoids all DP work for roughly half of all inputs.

Lines 4–6 — set target and initialise dp. target = total / 2. The dp set holds every subset-sum reachable so far; it starts as {0} because an empty selection always sums to zero.

Lines 8–13 — iterate nums, snapshot each round. For each num we take a snapshot of the current dp set before modifying it. This prevents using num more than once per round (the 0/1 constraint). Then for every existing sum s, candidate s + numis added if it doesn't exceed target. If it equals target we short-circuit immediately.

Line 17 — final answer. After processing all numbers, dp.has(target) tells us whether target was ever reachable. At this point the early-exit inside the loop would have already fired if target was hit, so this handles the case where target is only confirmed at the very last step.

Complexity → O(n · target) time where target = total / 2; O(target) space for the dp set. The outer loop runs n times; the inner snapshot loop is bounded by the number of distinct reachable sums, which cannot exceed target + 1.

INTERVIEWFollow-ups they'll ask

"Return the actual partition, not just true/false?" Keep a parent map: for each new sum record which num and previous sum produced it. After finding target, back-trace to recover one subset.
"What if numbers can be negative or zero?" Negative numbers break the target-cap pruning (ns < target). Shift everything by the minimum value to make inputs positive, or remove the cap and track the full sum range.
"Can you reduce space further?" A boolean[target + 1] array iterated right-to-left is already O(target) — same asymptotically, but avoids Set overhead. This is the textbook 1-D DP table.
"Unbounded version — each element usable many times?" Drop the snapshot (just iterate dp directly without copying) and the solution becomes Coin Change / unbounded knapsack.
"What's the brute force and why is DP better?" Enumerate all 2ⁿ subsets — O(2ⁿ) time. DP collapses overlapping sub-problems: whether sum s is reachable is computed only once regardless of how many paths lead to it.

OPTIMAL 0/1 Knapsack

canPartition.ts
function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;          // odd sum — impossible
  const target = total / 2;

  const dp = new Set<number>([0]);             // reachable subset sums

  for (const num of nums) {
    const current = Array.from(dp);           // snapshot before this round
    for (const s of current) {
      const ns = s + num;
      if (ns === target) return true;          // found a valid partition
      if (ns < target) dp.add(ns);            // only keep sums ≤ target
    }
  }

  return dp.has(target);
}

ALT 1 Brute force — try every subset

O(2ⁿ) time · O(n) recursion space

Reduce to subset-sum, then enumerate every subset by recursively choosing "include or skip" for each number, asking if any subset hits total / 2. The exhaustive baseline before memoising.

approach-2.ts
function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false; // odd sum can't split evenly
  const target = total / 2;

  // Can the numbers from index i onward reach exactly 'remaining'?
  function dfs(i: number, remaining: number): boolean {
    if (remaining === 0) return true;
    if (remaining < 0 || i === nums.length) return false;
    // include nums[i], or skip it
    return dfs(i + 1, remaining - nums[i]) || dfs(i + 1, remaining);
  }

  return dfs(0, target);
}

Note → Each element doubles the search, so this is O(2ⁿ) in the worst case and times out past ~30 numbers. The DP version notices that only the set of reachable sums (≤ target) matters, collapsing the exponential tree into O(n · target) by reusing sums across branches.

MNEMONIC The one-liner

"Odd total? Impossible. Otherwise chase half the sum with a set, snapshotting each round."

TRIGGERS When you see _ → reach for _

"partition into two equal subsets"	subset-sum DP to total/2
"can any subset reach value X"	boolean dp set, snapshot per num
"0/1 constraint — each item used at most once"	snapshot or right-to-left array
"minimize difference between two partitions"	same skeleton, Last Stone Weight II

SKELETON The reusable shape

skeleton.ts
function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  const target = total / 2;
  const dp = new Set<number>([0]);
  for (const num of nums) {
    const current = Array.from(dp);
    for (const s of current) {
      const ns = s + num;
      if (ns === target) return true;
      if (ns < target) dp.add(ns);
    }
  }
  return dp.has(target);
}

FLASHCARDS Tap to flip

What is the first check and why?

total % 2 !== 0 → return false. An odd total can never split into two equal-integer halves.

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

For nums = [1, 5, 11, 5], what is target?

QUESTION 02

What is the very first check the algorithm makes, and why?

QUESTION 03

Why must you snapshot Array.from(dp) before the inner loop (or iterate right-to-left on a boolean array)?

QUESTION 04

What is the time complexity of the dp-set solution?

QUESTION 05

nums = [2, 2, 1]. Does canPartition return true or false?

QUESTION 06

What does dp contain after initialisation, before any number is processed?

QUESTION 07

How do you convert this to the unbounded (items usable many times) variant?

QUESTION 08

#416 · Partition Equal Subset SumIf the total sum is odd return false; otherwise find a subset summing to total÷2 via 0/1 knapsack — a boolean DP array updated right-to-left per number in O(n × sum) time.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Reduce to subset-sum at target = total / 2

RECIPE Odd-check → set of sums → scan

COST Complexity & alternatives

Space note

RUN IT Build reachable sums — stop when target is hit

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL 0/1 Knapsack

ALT 1 Brute force — try every subset

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _