Log inSign up
mediumLeetCodeNot Started

Partition Equal Subset Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

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 have sum 11).

### Example 2 - Input: nums = [1, 2, 3, 5] - Output: false - Explanation: The total sum is 11, which cannot be partitioned into equal integer subsets.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Reduce partition problems to subset sum queries.
  • Implement 0-1 knapsack boolean reachability.
  • Space-optimize to a 1D boolean array.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Partitioning array into two equal subsets.
  • Sum matching problem reducible to 0-1 Knapsack.

Algorithmic Decision Tree:

  • Check parity of total sum first.
  • If any single element > target, return false.

Connected Patterns:

Subset SumMinimum Subset Sum DifferenceTarget Sum

1. Recursive Inclusion / Exclusion

Intuition

Recursively decide whether to include or exclude each element to reach target = totalSum / 2.

Algorithm

  1. If totalSum % 2 != 0, return false.
  2. Define solve(idx, target).
  3. If target == 0, return true.
  4. If idx == n || target < 0, return false.
  5. Return solve(idx + 1, target - nums[idx]) || solve(idx + 1, target).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5using namespace std;
6
7class Solution {
8 bool solve(int idx, int target, const vector<int>& nums) {
9 if (target == 0) return true;
10 if (idx == nums.size() || target < 0) return false;
11 return solve(idx + 1, target - nums[idx], nums) || solve(idx + 1, target, nums);
12 }
13public:
14 bool canPartition(vector<int>& nums) {
15 int totalSum = accumulate(nums.begin(), nums.end(), 0);
16 if (totalSum % 2 != 0) return false;
17 return solve(0, totalSum / 2, nums);
18 }
19};
20
21int main() {
22 Solution sol;
23 vector<int> nums = {1, 5, 11, 5};
24 cout << (sol.canPartition(nums) ? "true" : "false") << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. 2D Tabulation DP

Intuition

Build an explicit 2D boolean array dp[n + 1][target + 1].

Algorithm

  1. Check parity of totalSum; let target = totalSum / 2.
  2. Initialize dp[n + 1][target + 1] with false; dp[i][0] = true.
  3. For i from 1 to n:
  4. For s from 1 to target:
  5. dp[i][s] = dp[i-1][s] || (s >= nums[i-1] ? dp[i-1][s - nums[i-1]] : false).
  6. Return dp[n][target].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5using namespace std;
6
7class Solution {
8public:
9 bool canPartition(vector<int>& nums) {
10 int totalSum = accumulate(nums.begin(), nums.end(), 0);
11 if (totalSum % 2 != 0) return false;
12 int target = totalSum / 2;
13 int n = nums.size();
14
15 vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
16 for (int i = 0; i <= n; ++i) dp[i][0] = true;
17
18 for (int i = 1; i <= n; ++i) {
19 for (int s = 1; s <= target; ++s) {
20 dp[i][s] = dp[i - 1][s];
21 if (s >= nums[i - 1]) {
22 dp[i][s] = dp[i][s] || dp[i - 1][s - nums[i - 1]];
23 }
24 }
25 }
26
27 return dp[n][target];
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<int> nums = {1, 5, 11, 5};
34 cout << (sol.canPartition(nums) ? "true" : "false") << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(n * target)
  • Space complexity: O(n * target)

3. Space-Optimized 1D Reverse Knapsack Array

Intuition

Use a single 1D boolean array of size target + 1 traversed in reverse from target down to num.

Algorithm

  1. Check if totalSum % 2 != 0; if so, return false.
  2. target = totalSum / 2.
  3. Initialize boolean array dp of size target + 1 with false; dp[0] = true.
  4. For each num in nums:
  5. For s from target down to num:
  6. dp[s] = dp[s] || dp[s - num].
  7. If dp[target] is true, return true early.
  8. Return dp[target].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5using namespace std;
6
7class Solution {
8public:
9 bool canPartition(vector<int>& nums) {
10 int totalSum = accumulate(nums.begin(), nums.end(), 0);
11 if (totalSum % 2 != 0) return false;
12 int target = totalSum / 2;
13
14 vector<bool> dp(target + 1, false);
15 dp[0] = true;
16
17 for (int num : nums) {
18 for (int s = target; s >= num; --s) {
19 dp[s] = dp[s] || dp[s - num];
20 }
21 if (dp[target]) return true;
22 }
23
24 return dp[target];
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<int> nums = {1, 5, 11, 5};
31 cout << (sol.canPartition(nums) ? "true" : "false") << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(n * target)
  • Space complexity: O(target)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive SearchO(2^n)O(n)Exhaustive branching over inclusion/exclusion.Overlapping subsets
2.2D TabulationO(n * target)O(n * target)Fill 2D boolean reachability table.Matrix allocation
3.1D Reverse Knapsack ArrayOptimalO(n * target)O(target)Single 1D boolean array traversed backwards.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Iterating forward in the 1D DP loop, turning the problem into Unbounded Knapsack.

Pitfall 2:

Missing the odd sum parity check at the beginning.

Crucial Edge Cases to Validate:

  • Array length < 2: Cannot be partitioned into two subsets; returns false.
  • Single element exceeds target: Cannot be partitioned; returns false.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that this is a direct reduction to the NP-complete Subset Sum problem, solved via pseudo-polynomial dynamic programming.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can we return false immediately if totalSum is odd?

Back to DSA Sheet