416. Partition Equal Subset Sum

At a Glance

Topic: dp-1d
Pattern: Dynamic Programming (0/1 knapsack reachability)
Difficulty: Medium
Companies: Facebook, Amazon, Google, Bloomberg, Microsoft
Frequency: High
LeetCode: 416

Problem (one-liner)

Given positive integers nums, determine whether they can be partitioned into two subsets with equal sum. Input: nums. Output: true/false.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

“Partition into two equal-sum subsets”
Total must be even; target half-sum is sum/2
Each number used at most once → 0/1 knapsack “can we hit target?”

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — 2^n subset sums.
Better — bitset / set of reachable sums — O(n * target) time.
Optimal — boolean 1D DP rolling over sums — O(n * target) time / O(target) space. <- pick this in interview.

Optimal Solution

Go

package main

func canPartitionFullTable(nums []int) bool {
	total := 0
	for _, value := range nums {
		total += value
	}
	if total%2 == 1 {
		return false
	}
	target := total / 2
	length := len(nums)
	table := make([][]bool, length+1)
	for index := range table {
		table[index] = make([]bool, target+1)
	}
	for index := 0; index <= length; index++ {
		table[index][0] = true
	}
	for itemIndex := 1; itemIndex <= length; itemIndex++ {
		value := nums[itemIndex-1]
		for sum := 1; sum <= target; sum++ {
			if sum < value {
				table[itemIndex][sum] = table[itemIndex-1][sum]
			} else {
				table[itemIndex][sum] = table[itemIndex-1][sum] || table[itemIndex-1][sum-value]
			}
		}
	}
	return table[length][target]
}

func canPartition(nums []int) bool {
	total := 0
	for _, value := range nums {
		total += value
	}
	if total%2 == 1 {
		return false
	}
	target := total / 2
	reachable := make([]bool, target+1)
	reachable[0] = true
	for _, value := range nums {
		for sum := target; sum >= value; sum-- {
			if reachable[sum-value] {
				reachable[sum] = true
			}
		}
	}
	return reachable[target]
}

JavaScript

function canPartitionFullTable(nums) {
	let total = 0;
	for (const value of nums) {
		total += value;
	}
	if (total % 2 === 1) return false;
	const target = total / 2;
	const length = nums.length;
	const table = Array.from({ length: length + 1 }, () =>
		new Array(target + 1).fill(false)
	);
	for (let index = 0; index <= length; index++) {
		table[index][0] = true;
	}
	for (let itemIndex = 1; itemIndex <= length; itemIndex++) {
		const value = nums[itemIndex - 1];
		for (let sum = 1; sum <= target; sum++) {
			if (sum < value) {
				table[itemIndex][sum] = table[itemIndex - 1][sum];
			} else {
				table[itemIndex][sum] =
					table[itemIndex - 1][sum] ||
					table[itemIndex - 1][sum - value];
			}
		}
	}
	return table[length][target];
}

function canPartition(nums) {
	let total = 0;
	for (const value of nums) {
		total += value;
	}
	if (total % 2 === 1) return false;
	const target = total / 2;
	const reachable = new Array(target + 1).fill(false);
	reachable[0] = true;
	for (const value of nums) {
		for (let sum = target; sum >= value; sum--) {
			if (reachable[sum - value]) {
				reachable[sum] = true;
			}
		}
	}
	return reachable[target];
}

Walkthrough

Input: nums = [1,5,11,5]

Total 22, target 11.
After processing 1: reachable {0,1}.
After 5: {0,1,5,6}.
After 11: includes 11 from 0+11.
Return true.

Invariant: after each number, reachable[sum] iff some subset of processed numbers sums to sum. Iterate sums descending to avoid reusing the same element twice in one pass.

Edge Cases

Total odd → false immediately
Single element → false for partition into two non-empty (problem usually implies two disjoint subsets; length 1 fails)
Large target still bounded by sum of nums

Pitfalls

Forward iteration on inner loop (turns 0/1 into unbounded)
Forgetting reachable[0]=true
Integer overflow when summing (use 64-bit if needed)

Variants

Partition into k equal-sum subsets → backtracking + memo (different complexity).
Count partitions → use integer DP instead of boolean.

Mind-Map Tags

#01-knapsack #subset-sum #partition #boolean-dp #medium