110. Partition Equal Subset Sum
View on NeetCode
View on LeetCode
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].
Example 2:
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
Constraints:
1 <= nums.length <= 2001 <= nums[i] <= 100
Solution
Key Insight
If we can partition the array into two equal subsets, each subset must sum to total_sum / 2. This reduces the problem to: “Can we find a subset that sums to target = total_sum / 2?”
This is the classic 0/1 Knapsack problem where each number can be used at most once.
Approach 1: Recursive DFS with Memoization (Most Intuitive)
This is the most intuitive approach - for each number, we make a binary decision: include it or skip it.
Implementation
from functools import lru_cache
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
# If total sum is odd, can't partition into two equal subsets
if total & 1:
return False
target = total // 2
# Optimization: sort descending to find answer faster
nums.sort(reverse=True)
if nums[0] > target:
return False
@lru_cache(None)
def dfs(i, remain):
# Found a valid subset!
if remain == 0:
return True
# Out of numbers or went over target
if i == len(nums) or remain < 0:
return False
# Two choices: include nums[i] or skip it
return dfs(i + 1, remain - nums[i]) or dfs(i + 1, remain)
return dfs(0, target)
How It Works
State: dfs(i, remain) = “Can we make sum remain using nums[i:]?”
Decision Tree Example: nums = [1, 5, 11, 5], target = 11
After sorting: [11, 5, 5, 1]
dfs(0, 11)
├─ Include 11: dfs(1, 0) → True ✓
└─ Skip 11: (not needed, already found answer)
Why sort descending? Trying larger numbers first often finds the answer faster or prunes invalid branches early.
Complexity
- Time: O(n × target) - at most n × target unique states to memoize
- Space: O(n × target) for memoization cache + O(n) call stack
Approach 2: Iterative 1D DP (Space Optimized)
This is the bottom-up version that builds all possible sums incrementally.
Implementation
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 # Can always make sum 0 (empty subset)
for num in nums:
# CRITICAL: Traverse from right to left to avoid using same element twice
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]
return dp[target]
Why Iterate Backwards?
The backwards iteration is critical! Here’s why:
# ❌ WRONG: Forward iteration
nums = [5], target = 10
dp = [T, F, F, F, F, F, F, F, F, F, F]
for s in range(5, 11): # Forward
dp[s] = dp[s] or dp[s - 5]
# s=5: dp[5] = T (correct)
# s=10: dp[10] = dp[10] or dp[5] = T (WRONG! Used 5 twice)
# ✓ CORRECT: Backward iteration
for s in range(10, 4, -1): # Backward
dp[s] = dp[s] or dp[s - 5]
# s=10: dp[10] = dp[10] or dp[5] = F (correct, 5 not used yet)
# s=5: dp[5] = T
Going backwards ensures we only look at the “previous iteration” data, not values we just updated.
Step-by-Step Trace
nums = [1, 5, 11, 5], target = 11
Initial: dp = [T, F, F, F, F, F, F, F, F, F, F, F]
After 1: dp = [T, T, F, F, F, F, F, F, F, F, F, F] # Can make: {0, 1}
After 5: dp = [T, T, F, F, F, T, T, F, F, F, F, F] # Can make: {0, 1, 5, 6}
After 11: dp = [T, T, F, F, F, T, T, F, F, F, F, T] # Can make: {0, 1, 5, 6, 11}
After 5: dp[11] = True ✓
Complexity
- Time: O(n × target)
- Space: O(target) - most space efficient!
Approach 3: 2D DP (Most Explicit)
This makes the state transitions more explicit but uses more space.
Implementation
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[i][s] = can we make sum s using first i elements
dp = [[False] * (target + 1) for _ in range(n + 1)]
# Base case: can always make sum 0
for i in range(n + 1):
dp[i][0] = True
for i in range(1, n + 1):
for s in range(1, target + 1):
# Don't include nums[i-1]
dp[i][s] = dp[i-1][s]
# Include nums[i-1] if possible
if s >= nums[i-1]:
dp[i][s] = dp[i][s] or dp[i-1][s - nums[i-1]]
return dp[n][target]
Complexity
- Time: O(n × target)
- Space: O(n × target)
Approach Comparison
| Aspect | Recursive DFS | 1D DP | 2D DP |
|---|---|---|---|
| Intuition | ⭐⭐⭐ Most intuitive | ⭐⭐ Requires understanding backwards iteration | ⭐⭐⭐ Clear state transitions |
| Space | O(n × target) | ⭐ O(target) - Best! | O(n × target) |
| Code Length | Medium | ⭐ Shortest | Longest |
| Optimization | Can sort + early exit | Only odd-sum check | Only odd-sum check |
| Learning Value | Best for first understanding | Best for interviews | Good for understanding DP transitions |
Recommendation:
- Learning: Start with recursive DFS
- Interview: Use 1D DP (shows you understand space optimization)
- Debugging: Use 2D DP (easier to trace)
Key Insights
-
Problem Reduction: Equal partition → Subset sum to target = total/2
-
Odd Sum Check: If total is odd, return False immediately
-
0/1 Knapsack Variant: Each number can be used at most once
- Recursive ≈ Iterative DP: They’re the same algorithm!
- Recursive: Top-down with memoization
- DP: Bottom-up tabulation
-
The Backwards Trick: In 1D DP, iterate from right to left to prevent using the same element twice in one iteration
- State Definition:
- Recursive:
dfs(i, remain)= “Can we makeremainusing nums[i:]?” - DP:
dp[s]= “Can we make sumsusing nums processed so far?”
- Recursive:
- Optimization Opportunities:
- Sort descending + try largest first (recursive)
- Early termination when target is found
- Space optimization: 1D vs 2D DP