How do you solve Partition Equal Subset Sum?

Use a top-down recursive DP with memoization. The recursion tries two choices at each index: include the current number in the subset or exclude it. If at any point the current sum equals the target (half the total sum), return True. If the current sum exceeds the target or the index goes beyond the array, return False. Memoize results to prune redundant paths. This approach guarantees correctness and efficiency.

What pattern does Partition Equal Subset Sum use?

The Pattern: Dynamic Programming (Top-Down Memoized Subset Sum) The Heuristic: When searching for a subset with a target sum, model the problem as a state space of (index, current_sum) and use memoization to prune repeated computations, transforming exponential brute force into polynomial time.

Partition Equal Subset Sum — Dynamic Programming

Q: What is the time complexity of Partition Equal Subset Sum?

O(n * target). The recursion explores states defined by index and current_sum. There are at most n indices and target sums, so the total states are O(n * target). Each state is computed once due to memoization.

Problem

Given a list of positive integers nums, return True if the array can be partitioned into two subsets such that the sums of the subsets are equal, and False otherwise.

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

Example

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

Output: True

The total sum is 22, which is even. The problem reduces to finding a subset that sums to 11. One valid subset is [11], and the other subset is [1, 5, 5], both summing to 11. The algorithm first checks if the total sum is even; if not, it returns False immediately. Then it uses recursion with memoization to explore whether a subset with sum equal to half the total exists. The recursion explores including or excluding each number, caching results to avoid redundant computations.

Approach

Straightforward Solution

A brute-force approach tries all subsets, which is exponential in time (O(2^n)) and infeasible for larger inputs.

Core Observation

The problem reduces to determining if there exists a subset of nums whose sum equals half of the total sum. This is because if such a subset exists, the rest of the elements form the other subset with the same sum.

Path to Optimal

Preview

Recognizing the problem as a subset sum problem, dynamic programming can be applied. The key insight is to use recursion with memoization to avoid recomputing states…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a top-down recursive DP with memoization. The recursion tries two choices at each index: include the current number in the subset or exclude it…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n * target)

The recursion explores states defined by index and current_sum. There are at most n indices and target sums, so the total states are O(n * target). Each state is computed once due to memoization.

Space

O(n * target)

The memo dictionary stores results for each (index, current_sum) state, requiring O(n * target) auxiliary space. The recursion stack depth is O(n), which is dominated by the memo size.

Solution

Python

1class Solution:
  def canPartition(self, nums: list[int]) -> bool:
      total_sum = sum(nums)
      if total_sum % 2 != 0:
          return False
      
      target = total_sum // 2
      memo = {}
9
      def dp(i, current_sum):
          if current_sum == target:
              return True
          if i >= len(nums) or current_sum > target:
              return False
          if (i, current_sum) in memo:
              return memo[(i, current_sum)]
          
          res = (dp(i + 1, current_sum + nums[i]) or
                 dp(i + 1, current_sum))
          
          memo[(i, current_sum)] = res
          return res
23
      return dp(0, 0)

Step-by-Step Solution

1

Check Total Sum Parity and Initialize Memoization

3total_sum = sum(nums)
4if total_sum % 2 != 0:
5    return False
7target = total_sum // 2
8memo = {}

Objective

To quickly determine if partitioning is impossible due to odd total sum and prepare memoization storage for DP.

Key Insight

If the total sum is odd, it's impossible to split the array into two equal subsets, so the function returns False immediately. This early exit avoids unnecessary computation. Initializing a memo dictionary prepares for caching recursive results, which is essential for pruning redundant computations in the DP recursion.

Interview Quick-Check

Core Logic

Checking total sum parity is a constant-time filter that prevents futile recursion when partitioning is impossible.

Common Pitfalls & Bugs

Forgetting to check sum parity leads to wasted computation and incorrect results on odd sums.

State & Boundaries

Memoization dictionary keys are tuples of (index, current_sum), representing unique recursion states.

2

Recursively Explore Subsets with Memoized DP

To determine if a subset summing to target exists by recursively including or excluding each number, while caching results to avoid recomputation.

3

Return Final Result from Recursive DP

To initiate the recursive search from the first index with zero accumulated sum and return whether a valid partition exists.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 11 Critical

if current_sum == target:

Return True if current_sum equals target.

Reaching the target sum means a valid subset has been found, so the recursion can terminate successfully.

Line 15 Critical

if (i, current_sum) in memo:

Recursively explore including or excluding the current number.

This line embodies the core decision: either add nums[i] to the current subset or skip it, exploring all subset combinations.

Line 4 Critical

if total_sum % 2 != 0:

Check if the total sum is odd.

If the total sum is odd, the array cannot be split into two equal subsets, so the function returns False immediately, avoiding unnecessary computation.

Full line-by-line criticality + rationale for all 17 lines available on Pro.

Test Your Understanding

Why is it necessary to memoize the results of subproblems defined by (index, current_sum) in this recursive solution?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Partition Equal Subset Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Partition Equal Subset Sum drill

or drill a free problem

1	`class Solution:`
2	`def canPartition(self, nums: list[int]) -> bool:`
3	`total_sum = sum(nums)`
4	`if total_sum % 2 != 0:`
5	`return False`
6
7	`target = total_sum // 2`
8	`memo = {}`
9
10	`def dp(i, current_sum):`
11	`if current_sum == target:`
12	`return True`
13	`if i >= len(nums) or current_sum > target:`
14	`return False`
15	`if (i, current_sum) in memo:`
16	`return memo[(i, current_sum)]`
17
18	`res = (dp(i + 1, current_sum + nums[i]) or`
19	`dp(i + 1, current_sum))`
20
21	`memo[(i, current_sum)] = res`
22	`return res`
23
24	`return dp(0, 0)`

3	`total_sum = sum(nums)`
4	`if total_sum % 2 != 0:`
5	`return False`
7	`target = total_sum // 2`
8	`memo = {}`