Difficulty: Medium1-D Dynamic Programming

Partition Equal Subset Sum

Problem in Plain English

Split the array into two groups with the same total, which is possible exactly when some subset adds up to half of the overall sum. Return true when such a subset exists and false otherwise.

Problem Statement

Given an integer array nums, return true if the array can be split into two subsets whose sums are equal, and false otherwise. Every element must belong to exactly one of the two subsets.

Both subsets share the same sum, so each one must total exactly half of the whole array sum. When the total sum is odd, no equal integer split exists.

The task therefore reduces to deciding whether some subset of nums adds up to total / 2.

Constraints

$1 \leq \mathrm{nums.length} \leq 200$ .
$1 \leq \mathrm{nums}[i] \leq 100$ .

Examples

Example 1

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

The total is 22. Select positions 0, 1 and 3 for [1, 5, 5], leaving [11]; both sums are 11. Selecting the single 11 also proves the same answer.

Example 2

Input: nums = [1, 2, 3, 5]
Output: false

The total is 11. Two equal integer sums would have to be 5.5 each, so parity alone rules out a partition.

Example 3

Input: nums = [2]
Output: false

The total is even and the target is 1, but the only subset sums are 0 and 2. Even total is necessary, not sufficient.

Example 4

Input: nums = [1, 2, 5]
Output: false

The total is 8 and the target is 4. Values 1 and 2 can make only 0, 1, 2 or 3, while 5 is too large. Reusing the same 1 or 2 would incorrectly create 4.

Intuition

If the total is 22, both groups must sum to 11. Finding just one subset of sum 11 is enough: every unused position forms the other group, whose sum is 22 - 11. In Example 1, [11] and [1, 5, 5] are both witnesses. Each array position can be selected once, even when its value repeats. Rather than remembering every subset, remember which totals those subsets can reach; different subsets with the same total have identical possibilities when the next number arrives.

Approaches

Recursive Subset Search

Solution Details

Reveal Recursive Subset Search: intuition, complexity, and code

Intuition

Choose whether to include each position in a subset that must reach half the total. The recursive state is the next index and the sum selected so far. Taking the current value or skipping it covers every subset, but many different paths revisit the same state. Positive values let us reject a branch as soon as it overshoots the target.

Step-by-Step Logic

Sum the array and reject odd totals. Otherwise set the target to half the total: Example 1 has total 22 and target 11.
Search from index 0 with selected sum 0. Before branching, return true for a sum of 11, or false at the end or above 11.
Try taking the current position first, then skipping it only if taking fails. In Example 1, taking 1 and then 5 reaches state (2, 6).
Taking 11 from state (2, 6) reaches (3, 17) and fails for overshooting. Skip that 11 instead to reach (3, 6).
Take the final 5 to reach (4, 11). The success test runs before the exhausted-array test, so this leaf returns true.
Propagate true through all waiting calls without exploring their skip branches. The chosen subset is [1, 5, 5].

Why It Works

At state (i, sum), positions before i have been decided exactly once. Every subset of the remaining positions either contains position i or does not, so the take and skip branches cover all possible completions. Reaching target proves a valid partition because the complement has the same sum. Reaching the end without target is failure; exceeding target is also failure because every remaining value is positive. By induction over the number of remaining positions, a call returns true exactly when a valid completion exists. Short-circuiting after the first successful branch preserves that decision.

Dry Run

Recursive Subset Search: variable states at each step
Event	Next index i	Selected sum	Remaining target	Decision / return
total check; enter root	0	0	11	22 is even; take 1
take 1	1	1	10	take first 5
take first 5	2	6	5	try taking 11
take 11	3	17	-6	overshoot: false
resume at (2, 6); skip 11	3	6	5	take final 5
take final 5	4	11	0	target reached: true
unwind to (3, 6)	3	6	5	take succeeded; skip not called; true
unwind to (2, 6)	2	6	5	skip succeeded; true
unwind to (1, 1)	1	1	10	take succeeded; skip not called; true
unwind to root (0, 0)	0	0	11	return true

Complexity Analysis

Time Complexity

O(2^n)

Space Complexity

O(n)

Let n be the array length. Each nonterminal call has at most two children, so the full search tree has at most 2^(n + 1) - 1 calls with constant work each, plus the O(n) sum scan. Early successes and positive-value pruning can reduce work but do not remove exponential worst cases. Only one path of at most n + 1 calls is live; no subset copies or memo table are allocated, and nums is not mutated. The total is at most 20000, so Java int and JavaScript numbers safely hold all sums. This teaching baseline is impractical for hard n = 200 failures.

Code

Solution.java

1class Solution {2    public boolean canPartition(int[] nums) {3        int total = 0;4        for (int x : nums) total += x;5        if (total % 2 != 0) return false;6        return dfs(nums, 0, 0, total / 2);7    }8
9    private boolean dfs(int[] nums, int i, int sum, int target) {10        if (sum == target) return true;11        // Positive values cannot undo an overshoot; success must precede exhaustion.12        if (i >= nums.length || sum > target) return false;13        // Advancing on both branches uses each position at most once.14        return dfs(nums, i + 1, sum + nums[i], target)15            || dfs(nums, i + 1, sum, target);16    }17}

Hints

Hint 1

If one group sums to S, what sum must its complement have? Start with the total and its parity.

Hint 2

An even total still needs a subset of half that total. At each position choose take or skip; equal values at different positions are separate choices.

Hint 3

Store a flag for each reachable sum, starting with sum 0. A new x extends an old sum j - x to j.

Hint 4

Compress to one row by scanning sums downward. Scanning upward would let a freshly updated entry reuse the same position.

Edge Cases

One value, such as [2], has no half-total subset even though the total is even.
Odd totals such as [1, 2, 3, 5] fail before either search or table allocation.
An even total with no target witness, such as [1, 2, 5], must return false; parity is only an initial filter.
Repeated values such as [2, 2, 2, 2] can be selected at distinct positions, yielding two groups of sum 4.
An element larger than target, such as 8 in [1, 2, 3, 8], cannot enter the target subset. The other values cannot reach 7 either.

Common Mistakes and Interview Tips

Scanning sums upward changes zero-one selection into unlimited reuse. On [1, 2, 5], repeatedly extending with the first 1 incorrectly marks target 4.
Initializing every table entry false, including dp[0], removes the empty-subset base case and prevents any sum becoming reachable.
Checking exhausted recursion before success rejects a solution that uses the last position, as the [1, 5, 5] branch of Example 1 does.
Greedy choice can strand the remainder: in [3, 3, 3, 4, 5, 6], target 12 is reachable as 5 + 4 + 3, but descending greedy chooses 6 + 5 and cannot fill the remaining 1.
Calling the numeric-target table polynomial in the number of input bits hides its pseudo-polynomial dependence on T; explain both the target bound and the descending-update invariant.

Key Takeaway

When the question is whether some subset hits an exact total, convert it to a target-sum check and track reachable sums with a 1D table scanned backwards.