Free lesson · DSA Mastery - Interview Prep, End to End

Partition Equal Subset Sum

Hard12 min readdsadynamic-programming

Partition Equal Subset Sum

Partition Equal Subset Sum is the gentlest first application of the 0/1 knapsack pattern: given an array of positive integers, decide whether it can be split into two subsets of equal sum. The key reduction is that two equal halves each sum to total / 2, so the question becomes "is there a subset summing to exactly total/2?" - a feasibility (boolean) 0/1 knapsack where the capacity is total/2 and each number is an item whose "weight" is its value. It shows how a partitioning question collapses into a subset-sum knapsack, introducing the boolean "can we hit exactly this sum?" flavor that recurs throughout the sub-group. We present the 2-D boolean DP (canonical) and the 1-D space-optimized version (optimal).

The insight: if the array splits into two equal-sum subsets, the total must be even (an odd total cannot split into two equal integer halves), and each subset sums to exactly total/2. Finding one such subset automatically determines the other (the remaining elements). So the whole partition question reduces to a single subset-sum feasibility check: can any subset of the numbers sum to exactly total/2? That is a 0/1 knapsack with capacity total/2, where each number is an item of that "weight," and we ask whether the capacity can be filled exactly.

The Problem

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal, or false otherwise.

Example 1:

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

Explanation: The array can be partitioned as [1,5,5] and [11], both summing to 11.

Example 2:

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

Explanation: The array cannot be partitioned into equal-sum subsets (total 11 is odd).

Constraints:

1 <= nums.length <= 200; 1 <= nums[i] <= 100.

Approaches Overview

#	Approach	Time	Space	Verdict
1	2-D boolean subset-sum DP	O(n · target)	O(n · target)	Canonical
2	1-D space-optimized (backward loop)	O(n · target)	O(target)	Optimal

If the total is odd, return false immediately. Otherwise set target = total / 2 and ask whether a subset sums to exactly target. The 2-D DP defines dp[i][s] = can a subset of the first i numbers sum to exactly s? The transition is include/exclude: dp[i][s] = dp[i-1][s] OR dp[i-1][s - nums[i-1]]. The answer is dp[n][target]. Since each row reads only the previous, a single 1-D boolean array with a backward capacity loop gives O(target) space - the 0/1 knapsack signature.

Approach 1: 2-D Boolean Subset-Sum DP - Canonical

The Idea

Reduce to subset sum. If total is odd, no equal partition exists. Otherwise let target = total / 2. Define dp[i][s] = true if some subset of the first i numbers sums to exactly s. For each number, either exclude it (reachability unchanged: dp[i-1][s]) or include it if it fits (dp[i-1][s - nums[i-1]]). A sum s is reachable if either holds. Base case: dp[i][0] = true (the empty subset sums to 0). The answer is dp[n][target].

Logic Flowchart

graph TD
    A["total odd? return false"] --> B["target = total / 2"]
    B --> C["dp[i][0] = true (empty subset sums to 0)"]
    C --> D["for each item i, each sum s:"]
    D --> E{"include nums[i-1]?"}
    E -->|exclude| F["dp[i-1][s]"]
    E -->|include if fits| G["dp[i-1][s - nums[i-1]]"]
    F --> H["dp[i][s] = exclude OR include"]
    G --> H
    H --> D
    D --> I["return dp[n][target]"]

    style A fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows Partition Equal Subset Sum: reject odd totals, set the target to half the total, then fill a boolean table where each sum is reachable by either excluding or including the current number, returning whether the target is reachable.

Code

public static boolean canPartition(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false;                    // odd total cannot split equally
    int target = total / 2;
    int n = nums.length;
    boolean[][] dp = new boolean[n + 1][target + 1];
    for (int i = 0; i <= n; i++) dp[i][0] = true;        // empty subset sums to 0
    for (int i = 1; i <= n; i++) {
        for (int s = 1; s <= target; s++) {
            dp[i][s] = dp[i - 1][s];                      // exclude nums[i-1]
            if (nums[i - 1] <= s)                          // include if it fits
                dp[i][s] = dp[i][s] || dp[i - 1][s - nums[i - 1]];
        }
    }
    return dp[n][target];
}

// Usage:
// canPartition([1,5,11,5]) -> true
// canPartition([1,2,3,5]) -> false

This Java code solves Partition Equal Subset Sum with a two-dimensional boolean table: it rejects odd totals, then marks each sum reachable by excluding or including each number, returning whether half the total is reachable.

Step-by-Step Walkthrough

Tracing canPartition([1,5,11,5]) (total 22, target 11):

graph LR
    F0["total=22, target=11"]
    F1["reachable sums after 1: {0,1}"]
    F2["after 5: {0,1,5,6}; after 11: {0,1,5,6,11,...}"]
    F3["11 reachable → return true"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough partitions one, five, eleven, five: the target is eleven, and as numbers are added the reachable sums grow to include eleven, so the answer is true.

Result: true.

Complexity

Time: O(n · target) - fill the table once. Space: O(n · target) for the 2-D table.

Approach 2: 1-D Space-Optimized - Optimal

The Idea

Each row reads only the previous row, so a single boolean array suffices. Iterate the sum backwards (from target down to nums[i-1]) so that each number is used at most once - the 0/1 knapsack signature. dp[s] becomes reachable if it was already, or if dp[s - nums[i-1]] was reachable before this number.

Code

public static boolean canPartitionOptimized(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false;
    int target = total / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;                                        // empty subset sums to 0
    for (int num : nums)
        for (int s = target; s >= num; s--)              // BACKWARD: each number used once
            dp[s] = dp[s] || dp[s - num];
    return dp[target];
}

// Usage: canPartitionOptimized([1,5,11,5]) -> true

This Java code solves Partition Equal Subset Sum with a single boolean array and a backward sum loop, ensuring each number is used once, returning whether half the total is reachable.

Complexity

Time: O(n · target). Space: O(target) - a single boolean array.

Complexity Comparison

Approach	Time	Space	Key Idea
2-D boolean DP	O(n · target)	O(n · target)	dp[i][s] = exclude OR include
1-D backward loop	O(n · target)	O(target)	Single array, backward sum loop = each number once

Both decide the same reachability; the 1-D version collapses the table to one array using the backward loop that enforces "each number once." The central lesson is the reduction: an equal-partition question becomes a subset-sum feasibility check (capacity total/2), solved by the boolean 0/1 knapsack. Recognizing that reduction is the whole problem; the DP is then routine.

Variations & Follow-ups

Why does equal partition reduce to subset sum, and why check parity first?

The reduction is the heart of the problem. Suppose the array can be split into two subsets A and B with sum(A) = sum(B). Since A and B together contain every element, sum(A) + sum(B) = total. Combined with sum(A) = sum(B), this forces sum(A) = sum(B) = total / 2. So an equal partition exists if and only if some subset sums to exactly total / 2 - finding that subset A automatically leaves B as the rest, with the matching sum. This converts a question about splitting into two balanced groups into a question about finding one subset with a specific sum, which is exactly 0/1 knapsack (subset sum) with capacity total/2. Why check parity (odd total) first? Because total / 2 must be an integer for two equal integer-sum halves to exist. If total is odd, total / 2 is not an integer, so no two subsets of integers can each sum to it - the partition is impossible, and we return false immediately (Example 2: total 11 is odd → false). This parity check is a cheap O(1) pre-filter that handles a whole class of inputs before any DP. The general lesson: reductions turn unfamiliar problems into known ones (here, partition → subset sum), and necessary conditions (like even total) provide quick rejections. Recognizing "two equal groups" → "subset summing to half" is a transferable move; it appears again in Last Stone Weight II (minimize the difference between two groups → subset sum closest to half) later in this sub-group. Whenever a problem asks about balancing or splitting a collection by sum, think "subset sum to (some fraction of) the total."

Why does the backward loop enforce "each number used once"?

This is the single most important mechanical detail of 0/1 knapsack, and Partition Equal Subset Sum is a clean place to internalize it. In the 1-D optimization, dp[s] should mean "is sum s reachable using the numbers considered so far?" When processing number num, the transition dp[s] = dp[s] || dp[s - num] says "s is reachable if it already was, or if s - num was reachable before adding num (then add num)." The phrase before adding num is critical: dp[s - num] must reflect reachability without the current number, so that adding num uses it once. If we iterate s forward (low to high), then by the time we compute dp[s], the cell dp[s - num] may have already been updated in this same round to include num - so using it would add num a second time, allowing the number to be reused. Iterating s backward (high to low) guarantees dp[s - num] is still the previous round's value (not yet touched this round, since we process higher s first), so num is added at most once. The loop direction thus encodes the problem semantics: backward = each item once (0/1 knapsack); forward = items reusable (unbounded knapsack, the next sub-group). This is not a stylistic preference - it changes which problem you solve. A forward loop here would wrongly report sums reachable by reusing a number multiple times, breaking the subset-sum semantics (where each array element is available once). Understanding why - that the backward loop preserves the "previous row" values that "use each item once" requires - lets you confidently collapse any 0/1 knapsack to 1-D, and warns you that the unbounded variant (reuse allowed) deliberately uses the forward loop. This loop-direction distinction is the cleanest line between the two knapsack families.

How do you recover the actual partition, not just its existence?

The boolean DP answers whether an equal partition exists, but interviewers often ask to reconstruct one subset. Two standard techniques. Backtracking through the 2-D table: after filling dp[i][s], start at dp[n][target] and walk backward. At each dp[i][s], ask: was this reachable by excluding item i (i.e., is dp[i-1][s] true)? If so, item i is not in the subset; move to dp[i-1][s]. Otherwise it must have been reachable by including item i (dp[i-1][s - nums[i-1]] is true); record item i as chosen and move to dp[i-1][s - nums[i-1]]. Continue until s = 0. The recorded items form one subset (summing to target); the rest form the other. This requires the full 2-D table (the 1-D version discards the history needed to backtrack). Tracking parent choices: alternatively, store, for each reachable (i, s), which choice (include/exclude) achieved it, then follow those pointers back. The general principle: the DP table encodes not just the answer but the path to it, and reconstruction walks that path backward, at each step asking which transition produced the current cell. This reconstruction skill applies to all knapsack-family problems (recover the chosen items), to subsequence DPs (recover the subsequence), and to grid/string DPs (recover the path or alignment). The trade-off: reconstruction generally needs the full 2-D table (O(n · target) space), so if you only need the existence answer, the 1-D version is leaner; if you need the actual subset, keep the 2-D table. Knowing both - the space-efficient existence check and the table-walking reconstruction - covers both common interview asks.

How does this generalize across the 0/1 knapsack sub-group?

Partition Equal Subset Sum is the feasibility/boolean flavor of 0/1 knapsack - "can we hit exactly this sum?" - and it seeds the rest of the sub-group. Last Stone Weight II (a later topic) generalizes it from "exactly total/2" to "as close as possible to total/2": instead of a boolean "is total/2 reachable," it finds the largest reachable sum ≤ total/2, then the answer (minimum difference between two groups) is total - 2 × thatSum. The same subset-sum table, read differently. Target Sum is the counting flavor - after an algebraic reduction (assigning +/- signs reduces to "find subsets with a particular sum"), it counts how many subsets hit a target, changing the boolean OR to an integer +. Ones and Zeroes adds a second capacity dimension (count of 0s and count of 1s), making the state 3-D (item, zeros, ones) - the same include/exclude logic with two budgets. Profitable Schemes is a counting knapsack with two constraints (members used and minimum profit). All five share the include/exclude transition and the "subset under a budget" structure; they differ in (a) the objective (boolean feasibility / count / optimize), which sets the combining operator (OR / + / max/min), and (b) the number and kind of capacity dimensions. Recognizing this lets you adapt instantly: identify what plays "capacity" (a sum, a count of items, a profit threshold), what plays "weight/value," and what the objective is (can we / how many / best). Partition Equal Subset Sum establishes the simplest case - one capacity (total/2), boolean objective - so the richer variants are clearly "the same knapsack with more dimensions or a different combining operator." The transferable skill is the recognition and reduction: see "subset under a budget," map the roles, pick the operator for the objective.

What about edge cases?

Odd total (Example 2): Immediate false; no integer half exists.
Single element: Cannot split into two non-empty equal subsets unless... actually a single positive element has odd-or-even total equal to itself; if it is the only element, one side is empty (sum 0) and the other is nums[0] > 0, so false (the target total/2 is reachable only if a subset sums to it, and the empty subset sums to 0 ≠ target).
All elements equal: Partition possible iff the count is even (and total even); the DP handles it.
Large target: With up to 200 elements of value up to 100, total ≤ 20000, so target ≤ 10000 - the table is bounded and the DP is efficient.
Element larger than target: It cannot be in the half summing to target; the "if it fits" check skips it for those sums.

Common Interview Pitfalls

Skipping the parity check. An odd total can never split equally; check and return false first.
Using a forward sum loop in the 1-D version. That allows reusing a number (unbounded knapsack); 0/1 requires the backward loop.
Forgetting dp[0] = true. The empty subset sums to 0; this base case seeds the reachability.
Confusing the objective. This is feasibility (boolean OR), not counting or maximizing; use ||, not + or max.

Why This Topic Matters

Partition Equal Subset Sum is the first 0/1 knapsack application and teaches the core reduction: splitting into two equal-sum subsets is possible iff some subset sums to exactly total/2, turning a partitioning question into a subset-sum feasibility check (capacity total/2, each number an item of that weight). It establishes the boolean "can we hit exactly this sum?" flavor, the parity pre-filter, and - crucially - the backward capacity loop that enforces "each number used once," the mechanical signature distinguishing 0/1 from unbounded knapsack. It also previews subset reconstruction by walking the table backward.

The next topic, Target Sum, is the counting flavor of the same machine: given an array and a target, you assign a + or - sign to each number and count how many sign assignments make the signed sum equal the target. A neat algebraic reduction - letting P be the subset assigned + and N the subset assigned -, with sum(P) - sum(N) = target and sum(P) + sum(N) = total, giving sum(P) = (target + total) / 2 - converts it into "count the number of subsets summing to (target + total)/2," a counting 0/1 knapsack. It shows that changing the objective from "can we?" (boolean OR) to "how many ways?" (integer +) turns the feasibility knapsack into a counting knapsack, while introducing the powerful technique of algebraically transforming a signed-sum problem into a subset-sum problem.

Back to DSA Mastery - Interview Prep, End to End