Partition Equal Subset Sum

Description

Given an integer array nums, determine whether you can split the array into two non-empty subsets such that the sum of elements in each subset is identical.

Every element in the original array must appear in exactly one of the two subsets — you cannot leave any element out, and you cannot place the same element in both subsets.

Return true if such a partition is possible, or false otherwise.

Examples

Example 1

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

Output: true

Explanation: The array can be split into two subsets: {1, 5, 5} and {11}. Both subsets have a sum of 11, confirming an equal partition exists.

Example 2

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

Output: false

Explanation: The total sum is 1 + 2 + 3 + 5 = 11, which is odd. An odd total can never be divided equally into two integer sums, so no valid partition exists.

Example 3

Input: nums = [3, 3, 3, 4, 5]

Output: true

Explanation: Total sum = 18, so each subset must sum to 9. The subset {4, 5} sums to 9, and the remaining elements {3, 3, 3} also sum to 9.

Constraints

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 100

Editorial

Brute Force

Intuition

The most natural way to approach this problem is to think about what "partition into two equal-sum subsets" really means. If the total sum of the array is S, then each subset must sum to exactly S/2. If S is odd, we can immediately return false — there is no way to split an odd number equally into two integers.

Once we know the target is S/2, the problem reduces to: can we pick a subset of elements that sums to exactly S/2? This is the classic Subset Sum problem.

The simplest strategy is brute force: try every possible subset of the array and check whether any of them sums to the target. For each element, we have two choices — include it in our subset or exclude it. This naturally leads to a recursive approach where we branch on each element.

Step-by-Step Explanation

Let's trace through with nums = [1, 5, 11, 5]:

Step 1: Compute total sum = 1 + 5 + 11 + 5 = 22. Since 22 is even, target = 22 / 2 = 11. We need to find a subset that sums to 11.

Step 2: Call solve(index=3, remaining=11). We start from the last element and work backwards. Consider arr[3] = 5: include it or exclude it.

Step 3: Branch 1 — Include 5: Call solve(2, 6). Now consider arr[2] = 11. Since 11 > 6, we cannot include it. Skip to solve(1, 6).

Step 4: At solve(1, 6), consider arr[1] = 5. Include 5: call solve(0, 1). Now consider arr[0] = 1.

Step 5: Include 1: call solve(-1, 0). Remaining = 0 — base case reached! We found subset {1, 5, 5} that sums to 11.

Step 6: Propagate TRUE back up the call chain: solve(0,1)→true, solve(1,1)→true, solve(2,6)→true, solve(3,6)→true.

Step 7: Branch 2 — Exclude 5: call solve(2, 11). Consider arr[2] = 11. Include 11: call solve(1, 0). Remaining = 0 — another valid subset {11}.

Step 8: Root call returns TRUE. The array can be partitioned into {1, 5, 5} and {11}.

Recursive Subset Sum Exploration — Watch how the recursion branches on each element (include or exclude), exploring all subsets until finding one that sums to the target.

Algorithm

Compute the total sum of the array. If odd, return false immediately.
Set target = totalSum / 2.
Define a recursive function solve(index, remaining):
- If remaining == 0, return true (found a valid subset).
- If index < 0 or remaining < 0, return false (exhausted items or overshot).
- Try two choices:
  a. Include current element: solve(index - 1, remaining - nums[index])
  b. Exclude current element: solve(index - 1, remaining)
- Return true if either choice succeeds.
Call solve(n - 1, target) and return the result.

Code

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        if (totalSum % 2 != 0) return false;
        int target = totalSum / 2;
        return solve(nums, nums.size() - 1, target);
    }

private:
    bool solve(vector<int>& nums, int index, int remaining) {
        if (remaining == 0) return true;
        if (index < 0 || remaining < 0) return false;
        // Include current element OR exclude it
        return solve(nums, index - 1, remaining - nums[index])
            || solve(nums, index - 1, remaining);
    }
};

class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return False
        target = total_sum // 2
        return self.solve(nums, len(nums) - 1, target)

    def solve(self, nums, index, remaining):
        if remaining == 0:
            return True
        if index < 0 or remaining < 0:
            return False
        # Include current element OR exclude it
        return (self.solve(nums, index - 1, remaining - nums[index])
                or self.solve(nums, index - 1, remaining))

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        if (totalSum % 2 != 0) return false;
        int target = totalSum / 2;
        return solve(nums, nums.length - 1, target);
    }

    private boolean solve(int[] nums, int index, int remaining) {
        if (remaining == 0) return true;
        if (index < 0 || remaining < 0) return false;
        // Include current element OR exclude it
        return solve(nums, index - 1, remaining - nums[index])
            || solve(nums, index - 1, remaining);
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each element we make two recursive calls (include or exclude). In the worst case, no early termination occurs, and the recursion tree has 2^n leaf nodes. For n = 200 (the constraint upper bound), 2^200 is astronomically large — far beyond any practical time limit.

Space Complexity: O(n)

The recursion depth equals n (we process one element per level), so the call stack uses O(n) space. No additional data structures are used.

Why This Approach Is Not Efficient

The brute force recursion explores up to 2^n subsets. With n up to 200, this means up to 2^200 ≈ 10^60 operations — utterly infeasible.

The root cause of this explosion is overlapping subproblems. Many different paths in the recursion tree arrive at the same (index, remaining) state. For example, including element A then excluding element B leads to the same remaining sum as excluding A then including B (if they have the same value). The brute force recomputes each of these states from scratch every time.

The key insight: if we remember the result of each unique (index, remaining) state, we never recompute it. There are at most n × target distinct states, where target = totalSum/2. With n ≤ 200 and each element ≤ 100, target ≤ 10,000, giving at most 200 × 10,000 = 2,000,000 states — perfectly manageable. This observation leads us to dynamic programming.

Chart comparing exponential O(2^n) recursion growth versus polynomial O(n × target) dynamic programming

Better Approach - 2D Dynamic Programming

Intuition

Instead of recomputing overlapping subproblems, we build a table that stores the answer to every possible subproblem.

Define dp[i][j] = true if we can form sum j using some subset of the first i elements. We build this table row by row:

Base case: dp[0][0] = true (we can form sum 0 by picking nothing). dp[0][j] = false for j > 0 (cannot form a positive sum with zero items).
Transition: For each new item nums[i-1], we either exclude it (dp[i][j] = dp[i-1][j]) or include it if j ≥ nums[i-1] (dp[i][j] = dp[i-1][j - nums[i-1]]).

Think of it like packing a knapsack with a weight limit of target. For each item, you decide: does adding this item help reach the exact weight? The table systematically records every reachable weight.

After processing all items, dp[n][target] tells us whether the full target sum is achievable.

Step-by-Step Explanation

Let's trace through with nums = [1, 5, 11, 5], target = 11:

Step 1: Initialize dp table. dp[0][0] = 1 (true). All other dp[0][j] = 0 (false). With zero items, only sum 0 is achievable.

Step 2: Process item 1 (value=1). dp[1][0] = 1 — sum 0 always achievable (take nothing).

Step 3: dp[1][1] = dp[0][1] OR dp[0][0] = 0 OR 1 = 1. Including item 1 makes sum 1 reachable.

Step 4: dp[1][5] = dp[0][5] OR dp[0][4] = 0 OR 0 = 0. Cannot reach sum 5 with just {1}. Rest of row 1 is also 0.

Step 5: Process item 5 (value=5). dp[2][5] = dp[1][5] OR dp[1][0] = 0 OR 1 = 1. Item 5 alone reaches sum 5.

Step 6: dp[2][6] = dp[1][6] OR dp[1][1] = 0 OR 1 = 1. Items {1, 5} together make sum 6.

Step 7: dp[2][11] = dp[1][11] OR dp[1][6] = 0 OR 0 = 0. Still cannot reach target 11 with just {1, 5}.

Step 8: Process item 11 (value=11). dp[3][11] = dp[2][11] OR dp[2][0] = 0 OR 1 = 1. Including item 11 alone makes sum 11 — target reached!

Step 9: Process item 5 (value=5). dp[4][11] = dp[3][11] OR dp[3][6] = 1 OR 1 = 1. Already achievable from previous row.

Result: dp[4][11] = 1 → TRUE. The array can be partitioned.

2D DP Table — Subset Sum Construction — Watch how the dp table fills row by row. Each cell dp[i][j] answers: can we form sum j using the first i items?

Algorithm

Compute totalSum. If odd, return false. Set target = totalSum / 2.
Create a 2D boolean table dp of size (n+1) × (target+1), initialized to false.
Set dp[i][0] = true for all i (sum 0 is always achievable).
For each item i from 1 to n:
- For each sum j from 1 to target:
  - dp[i][j] = dp[i-1][j] (exclude item i)
  - If j ≥ nums[i-1]: dp[i][j] = dp[i][j] OR dp[i-1][j - nums[i-1]] (include item i)
Return dp[n][target].

Code

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        if (totalSum % 2 != 0) return false;
        int target = totalSum / 2;
        int n = nums.size();

        vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
        for (int i = 0; i <= n; i++) dp[i][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][target];
    }
};

class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return False
        target = total_sum // 2
        n = len(nums)

        dp = [[False] * (target + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = True

        for i in range(1, n + 1):
            for j in range(1, target + 1):
                dp[i][j] = dp[i - 1][j]
                if j >= nums[i - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j - nums[i - 1]]

        return dp[n][target]

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        if (totalSum % 2 != 0) return false;
        int target = totalSum / 2;
        int n = nums.length;

        boolean[][] dp = new boolean[n + 1][target + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][target];
    }
}

Complexity Analysis

Time Complexity: O(n × target)

We fill a table with n rows and target+1 columns. Each cell takes O(1) to compute (a lookup and a boolean OR). With n ≤ 200 and target ≤ 10,000, this is at most 2,000,000 operations — very fast.

Space Complexity: O(n × target)

The 2D dp table stores (n+1) × (target+1) boolean values. In the worst case, this is 201 × 10,001 ≈ 2 million booleans. While manageable, this space usage can be reduced — each row only depends on the previous row, so we don't need to store the entire table.

Why This Approach Is Not Efficient

The 2D DP approach runs in O(n × target) time, which is efficient enough. However, it uses O(n × target) space for the full table — up to ~2 million booleans.

The critical observation is that each row of the table depends only on the previous row. When computing dp[i][j], we only look at dp[i-1][j] and dp[i-1][j - nums[i-1]]. We never look at dp[i-2] or earlier rows.

This means we can compress the entire 2D table into a single 1D array of size target+1, reducing space from O(n × target) to O(target). The trick is to iterate the inner loop right to left so that we use the "old" values (from the previous row) before overwriting them.

Optimal Approach - Space-Optimized 1D DP

Intuition

We replace the 2D table with a single boolean array dp of size target+1, where dp[j] means "can we form sum j using the items processed so far?"

For each new item, we scan dp from right to left. Why right to left? If we scanned left to right, updating dp[j] would use the already-updated dp[j - num] from the current item — effectively using the same item twice. Scanning right to left ensures dp[j - num] still reflects the state before the current item, preserving the 0/1 knapsack constraint of using each item at most once.

Imagine a row of light switches, one per possible sum. Initially only switch 0 is ON. For each item with value v, you walk from right to left: if switch (j - v) is ON, you flip switch j ON too. After processing all items, check if switch target is ON.

Step-by-Step Explanation

Let's trace through with nums = [1, 5, 11, 5], target = 11:

Step 1: Initialize dp = [T, F, F, F, F, F, F, F, F, F, F, F]. Only sum 0 is achievable.

Step 2: Process nums[0] = 1. Scan j from 11 down to 1.

Step 3: j = 11: dp[11] = dp[11] OR dp[10] = F OR F = F. Cannot reach 11 with just item 1.

Step 4: j = 1: dp[1] = dp[1] OR dp[0] = F OR T = T. Including item 1 makes sum 1 reachable.
dp = [T, T, F, F, F, F, F, F, F, F, F, F]

Step 5: Process nums[1] = 5. Scan j from 11 down to 5.

Step 6: j = 11: dp[11] = dp[11] OR dp[6] = F OR F = F. Still cannot reach 11.

Step 7: j = 6: dp[6] = dp[6] OR dp[1] = F OR T = T. Items {1, 5} reach sum 6.

Step 8: j = 5: dp[5] = dp[5] OR dp[0] = F OR T = T. Item 5 alone reaches sum 5.
dp = [T, T, F, F, F, T, T, F, F, F, F, F]

Step 9: Process nums[2] = 11. Only j = 11 qualifies (j ≥ 11).

Step 10: j = 11: dp[11] = dp[11] OR dp[0] = F OR T = T! Target reached!
dp = [T, T, F, F, F, T, T, F, F, F, F, T]

Step 11: dp[target] = dp[11] = T → return true.

1D DP Array — Right-to-Left Sweep — Watch the dp array evolve as each item is processed. Scanning right to left ensures each item is used at most once.

Algorithm

Compute totalSum. If odd, return false. Set target = totalSum / 2.
Create a 1D boolean array dp of size target+1, initialized to false.
Set dp[0] = true.
For each num in nums:
- For j from target down to num:
  - dp[j] = dp[j] OR dp[j - num]
Return dp[target].

Code

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        if (totalSum % 2 != 0) return false;
        int target = totalSum / 2;

        vector<bool> dp(target + 1, false);
        dp[0] = true;

        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }
};

class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return False
        target = total_sum // 2

        dp = [False] * (target + 1)
        dp[0] = True

        for num in nums:
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]

        return dp[target]

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        if (totalSum % 2 != 0) return false;
        int target = totalSum / 2;

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }
}

Complexity Analysis

Time Complexity: O(n × target)

For each of the n elements, we iterate through at most target values in the inner loop. With n ≤ 200 and target ≤ 10,000, the maximum operations are 2,000,000 — identical to the 2D approach.

Space Complexity: O(target)

We use a single 1D array of size target + 1. Since each element is at most 100 and there are at most 200 elements, the maximum target is 200 × 100 / 2 = 10,000. So at most 10,001 booleans — a massive improvement over the 2D table's O(n × target) space. This is optimal because we need at least O(target) space to track which sums are achievable.

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Partition Equal Subset Sum

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - 2D Dynamic Programming

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Space-Optimized 1D DP

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis