Partition Equal Subset Sum: The 0/1 Knapsack in Disguise
Solve Partition Equal Subset Sum with the 0/1 knapsack subset-sum DP — intuition, a worked walkthrough, JavaScript code, and complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Partition Equal Subset Sum looks like a puzzle about splitting an array into two fair halves. It's actually a knapsack problem wearing a costume. Once you see the disguise, the whole thing collapses into a single, familiar question: which totals can I build by picking a subset of these numbers?
That reframe is worth internalizing, because the same reachable-sums machinery powers Coin Change, Target Sum, and half a dozen other "can I hit this number?" interview problems.
The problem
Given a non-empty array nums of positive integers, decide whether it can be split into two subsets whose sums are equal. Return true or false.
Input: nums = [1, 5, 11, 5]
Output: true // {1, 5, 5} sums to 11 and {11} sums to 11
Input: nums = [1, 2, 3, 5]
Output: false // total is 11 (odd) — no equal split existsOne observation shrinks the problem before you write any real logic. If the two halves are equal, each must sum to exactly total / 2. So the total has to be even — an odd total is an instant false. And once you fix the target at total / 2, you no longer care about "two subsets" at all. If one subset hits total / 2, whatever's left over automatically sums to total / 2 too. The question becomes: can any subset of nums sum to exactly total / 2?
The brute force baseline
The direct approach tries every subset. For each number you make a binary choice — include it in the running sum or skip it — and recurse:
function canPartition(nums) {
const total = nums.reduce((a, b) => a + b, 0);
if (total % 2 !== 0) return false;
const target = total / 2;
function subsetSum(index, remaining) {
if (remaining === 0) return true;
if (remaining < 0 || index === nums.length) return false;
// include nums[index], or skip it
return subsetSum(index + 1, remaining - nums[index]) ||
subsetSum(index + 1, remaining);
}
return subsetSum(0, target);
}This is correct but explores a full binary tree of choices: every element doubles the number of paths, so you're looking at O(2ⁿ) time. For 20 numbers that's a million calls; for 40 it's a trillion. The redundancy is the tell — the recursion reaches the same (index, remaining) state through many different include/skip orderings and re-solves it from scratch every time.
The key insight: track reachable sums
Instead of asking "does this specific path reach the target?", ask "which sums are reachable at all?" and build that answer up one number at a time.
Keep a set of every total you can currently make. Start with {0} — the empty subset always sums to zero. Now process each number n. For every sum t already in the set, you have two choices: skip n (the sum stays t) or take n (a new sum t + n becomes reachable). Union both into the next set.
The moment target appears in the set, a qualifying subset exists and you can stop. This is exactly the 0/1 knapsack / subset-sum pattern: each item is used at most once, and the "capacity" you're filling is total / 2. Collapsing all paths into one set of reachable sums is what turns exponential blowup into polynomial work.
The optimal solution
This mirrors the algorithm the visualizer steps through — a reachable-sums set that grows number by number:
var canPartition = function (nums) {
let sum = nums.reduce((acc, curr) => acc + curr, 0);
if (sum % 2) return false; // odd total can't split evenly
const target = sum / 2;
let dp = new Set([0]); // sums reachable so far; {} makes 0
for (const n of nums) {
const nextDP = new Set();
for (const t of dp) {
nextDP.add(t); // exclude n: keep sum t
nextDP.add(t + n); // include n: new sum t + n
}
dp = nextDP;
if (dp.has(target)) return true; // early exit — a valid subset exists
}
return false;
};Two things carry the performance. The dp set never grows past target + 1 distinct useful values, so each number does bounded work instead of branching. And the dp.has(target) check lets you bail the instant the target becomes reachable, without processing the remaining numbers — in the example below, the last 5 is never even touched.
Walkthrough
Trace nums = [1, 5, 11, 5]. The total is 22, so target = 11. The dp set starts as {0}.
| Step | i | n | dp before | include branches (t + n) | dp after | 11 reachable? |
|---|---|---|---|---|---|---|
| init | – | – | – | – | {0} | no |
| 1 | 0 | 1 | {0} | 0+1=1 | {0, 1} | no |
| 2 | 1 | 5 | {0, 1} | 0+5=5, 1+5=6 | {0, 1, 5, 6} | no |
| 3 | 2 | 11 | {0, 1, 5, 6} | 0+11=11, 12, 16, 17 | {0, 1, 5, 6, 11, 12, 16, 17} | yes → true |
At step 3 the branch 0 + 11 = 11 lands exactly on the target — the subset {11} alone reaches 11, and its complement {1, 5, 5} does too. The loop returns true immediately and the trailing 5 at index 3 is never processed. Every reachable sum you see in the visualizer's "Achievable Sums Set" is one entry of the dp set at that step.
Complexity
Let n be the number of elements and S the total sum (so target = S/2).
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute-force recursion | O(2ⁿ) | O(n) | every element doubles the paths; recursion depth n |
| Reachable-sums DP | O(n · S) | O(S) | each of n numbers scans at most S/2 reachable sums |
| Bottom-up boolean array | O(n · S) | O(S) | same recurrence, a boolean[target+1] in place of a Set |
The DP is pseudo-polynomial: it's linear in n but scales with the numeric value S, not just the count of items. That's fine for typical constraints (sums in the low thousands) and is the accepted solution. If the values were astronomically large, this bound would be the catch to flag.
Common mistakes
- Forgetting the odd-total short circuit. If
totalis odd, no equal split can exist. Skipping thesum % 2check wastes an entire DP pass and, worse, can make a non-integertargetslip through. - Not seeding the set with
0. The empty subset sums to zero. Without{0}indp, the very first number can never build on anything and the whole set stays empty. - Mutating
dpwhile iterating it. Addingt + nback into the same set you're looping over lets a single number get counted twice (turning it into an unbounded-knapsack bug). Build a freshnextDP, then swap — exactly as the code does. - Checking for the target only at the end. You can hit
targetpartway through. Testingdp.has(target)inside the loop enables the early exit and avoids needless work on the tail of the array.
Where this pattern shows up next
The "build up reachable states one item at a time" idea is the backbone of a whole family of DP problems:
- Coin Change II — the same knapsack skeleton, but counting the number of ways to reach a target instead of just whether it's possible.
- Word Break — reachability again, where the "sums" are string prefixes and each dictionary word is an item.
- Unique Paths — a grid DP that builds each cell's answer from smaller subproblems, the additive cousin of this boolean recurrence.
- Longest Increasing Subsequence — a different subsequence DP worth contrasting, since it optimizes a value rather than testing feasibility.
To watch the reachable-sums set fill in and the target light up, step through the Partition Equal Subset Sum visualizer one number at a time.
FAQ
Why is Partition Equal Subset Sum a 0/1 knapsack problem?
Because each number can be used at most once (that's the "0/1" part — take it or leave it), and you're trying to fill a fixed capacity of total / 2. The "value" and "weight" of each item are both just the number itself, and success means the filled sum equals the capacity exactly. Recognizing this lets you reuse the standard subset-sum recurrence instead of inventing something new.
Why does the total sum have to be even?
If the array splits into two subsets with equal sums, then each subset sums to total / 2. That value has to be a whole number, which is only possible when total is even. An odd total can never be divided into two equal integer halves, so you return false immediately without running the DP at all.
What is the time and space complexity?
The reachable-sums DP runs in O(n · S) time and O(S) space, where n is the number of elements and S is the total sum. Each of the n numbers scans at most S/2 previously reachable sums. This is pseudo-polynomial — efficient when S is modest, but it grows with the numeric magnitude of the sum, not just the element count.
Can I use a boolean array instead of a Set?
Yes, and it's the classic textbook form. Allocate dp = new Array(target + 1).fill(false) with dp[0] = true, then for each number iterate the capacity downward from target to n, setting dp[c] = dp[c] || dp[c - n]. The downward sweep is what keeps each number single-use. It has identical O(n · S) time and O(S) space; the Set version just makes the "reachable sums" idea more visually explicit.
What if the array contains a zero or a single element?
Zeros don't change any sum, so they're harmless — they simply never move the target closer. A single-element array can only be partitioned if that element is 0 (both halves empty-vs-zero), since one non-zero number alone can't be split. The even-total check and the {0} seed handle both cases correctly without special code.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.