AlgoMaster Logo

Partition Equal Subset Sum

Last Updated: March 28, 2026

medium
4 min read

Understanding the Problem

We need to decide whether it is possible to split the array into two groups where both groups have the same total. The first thing to notice is that if both subsets have equal sum, then each subset's sum must be exactly half of the total array sum. If the total sum is odd, there is no way to split it evenly, so we can immediately return false.

Once we know the target is totalSum / 2, the problem transforms into something more familiar: can we find a subset of nums that adds up to exactly target? This is the classic 0/1 Knapsack / Subset Sum problem. Each number is either included in the subset or it is not, and we want to know if any combination of included numbers hits the target exactly.

Key Constraints:

  • 1 <= nums.length <= 200 → With n up to 200, O(n^2) and even O(n sum) approaches are comfortably within time limits. Since max sum is 200 100 = 20,000, a DP table of size n * 10,000 (target = sum/2) is about 2 million entries, which is fine.
  • 1 <= nums[i] <= 100 → All values are positive, so the target sum is bounded by 10,000. This keeps the DP table manageable. Also, no zeros or negatives to worry about.

Approach 1: Brute Force (Recursion)

Intuition

The most natural starting point is to try every possible subset. For each element, we have two choices: include it in the first subset or exclude it. If at any point the running sum equals the target (totalSum / 2), we have found a valid partition.

This is essentially a depth-first search through the decision tree. At each level, we pick one element and branch into "take it" or "leave it." If the "take it" branch reaches exactly target, we return true. Otherwise, we backtrack and try the other option.

Algorithm

  1. Compute the total sum of the array. If it is odd, return false immediately.
  2. Set target = totalSum / 2.
  3. Define a recursive function canFind(nums, index, remaining) that returns true if we can form a sum of remaining using elements from index index onward.
  4. Base cases: if remaining == 0, return true. If remaining < 0 or index >= nums.length, return false.
  5. Recurse: try including nums[index] (subtract it from remaining) or excluding it (keep remaining the same).

Example Walkthrough

1Start: canFind(index=0, remaining=11)
0
1
index=0
1
5
2
11
3
5
1/6

Code

The brute force explores up to 2^n subsets, which is impossibly slow for n = 200. Many recursive calls solve the same subproblem repeatedly. What if we cached results so we never solve the same (index, remaining) pair twice?

Approach 2: Top-Down DP (Memoization)

Intuition

The brute force solution recomputes the same subproblems many times. The state of each recursive call is fully described by two values: the current index and the remaining sum we need to achieve. If we have already computed whether it is possible to form remaining from elements at positions index through n-1, we can just return that stored result.

This is a classic application of memoization. We keep a 2D memo table keyed by (index, remaining). Before doing any work, we check if we have seen this state before. If so, return the cached answer. If not, compute it, store it, and return.

Algorithm

  1. Compute total sum. If odd, return false. Set target = totalSum / 2.
  2. Create a memo table (2D array or hash map) initialized to "unvisited."
  3. Define canFind(index, remaining):
    • If remaining == 0, return true.
    • If remaining < 0 or index >= n, return false.
    • If memo[index][remaining] is already computed, return it.
    • Compute result by trying include/exclude, store in memo, and return.
  4. Return canFind(0, target).

Example Walkthrough

1Start: canFind(index=0, remaining=11)
0
1
index=0
1
5
2
11
3
5
1/6

Code

The memo table uses O(n * target) space. But each row only depends on the row below it, so we are storing n rows when we only need one. What if we used a bottom-up approach with a single 1D array?

Approach 3: Bottom-Up DP (1D Array)

Intuition

Instead of working top-down with recursion, we can build the solution bottom-up. We define dp[j] as a boolean: "can we form sum j using some subset of the elements we have processed so far?"

We start with dp[0] = true (we can always form sum 0 by taking nothing). Then for each number in the array, we update the DP array. If we could previously form sum j, then by including the current number we can now also form sum j + nums[i].

The key trick is iterating from right to left (from target down to nums[i]) when updating. If we iterated left to right, we might use the same element twice in a single subset. By going right to left, when we set dp[j] = true based on dp[j - nums[i]], we know that dp[j - nums[i]] reflects the state before the current element was considered.

Algorithm

  1. Compute total sum. If odd, return false. Set target = totalSum / 2.
  2. Create a boolean array dp of size target + 1, initialized to false. Set dp[0] = true.
  3. For each number num in the array:
    • For j from target down to num:
      • If dp[j - num] is true, set dp[j] = true.
  4. Return dp[target].

Example Walkthrough

1Initial: dp[0]=true (sum 0 is always reachable)
[T, F, F, F, F, F, F, F, F, F, F, F]
1/7

Code