416. Partition Equal Subset Sum - Explanation
Description
You are given an array of positive integers nums.
Return true if you can partition the array into two subsets, subset1 and subset2 where sum(subset1) == sum(subset2). Otherwise, return false.
Example 1:
Input: nums = [1,2,3,4]
Output: trueExplanation: The array can be partitioned as [1, 4] and [2, 3].
Example 2:
Input: nums = [1,2,3,4,5]
Output: falseConstraints:
1 <= nums.length <= 1001 <= nums[i] <= 50
Topics
Recommended Time & Space Complexity
You should aim for a solution as good or better than O(n * t) time and O(n * t) space, where n is the size of the input array and t is half the sum of the array elements.
Hint 1
If the sum of the array elements is not even, we can immediately return false. Think in terms of recursion, where we try to build a subset with a sum equal to half of the total sum. If we find such a subset, the remaining elements will automatically form another subset with the same sum. The entire array can also be considered as one subset, with the other being empty. Can you visualize this as a decision tree to process the array recursively?
Hint 2
We recursively iterate through the array with index i. At each step, we decide whether to include the current element in the subset or not. Instead of forming the subset explicitly, can you think of a better approach? Maybe you only need to track the subset sum rather than generating the subset itself.
Hint 3
We can track the subset sum using a variable curSum. At each step, we make two recursive calls. If adding the current element does not exceed the target, we include it. If either path leads to a solution, we immediately return true. Can you determine the base case for this recursion? All elements in the array are positive.
Hint 4
If curSum equals half the sum of the array elements, we return true. If index i goes out of bounds, we return false. This solution is exponential, but we can use memoization to cache recursive call results and avoid redundant computations. We can use a hash map or a 2D array with dimensions n * t, where n is the size of the input array and t is half the sum of the input array elements.
Prerequisites
Before attempting this problem, you should be comfortable with:
- Dynamic Programming (0/1 Knapsack Pattern) - This problem is a classic subset sum variant of the knapsack problem
- Recursion with Memoization - Essential for the top-down DP approach to avoid redundant calculations
- Subset Sum Problem - Core concept of determining if a subset with a target sum exists
- Space Optimization in DP - Techniques to reduce 2D DP to 1D using reverse iteration
1. Recursion
Intuition
The problem asks whether we can split the array into two subsets with equal sum.
Key observation:
- If the total sum is odd, it’s impossible → return
False. - Otherwise, the problem becomes:
Can we pick a subset whose sum is
totalSum / 2?
This is a classic subset sum decision problem.
Using recursion:
- At each index, we have two choices:
- Take the current number into the subset
- Skip the current number
- We keep reducing the target (
sum/2) until:- Target becomes
0→ success - We run out of numbers or target becomes negative → failure
- Target becomes
Algorithm
- Compute
totalSum = sum(nums) - If
totalSumis odd, returnfalse - Set
target = totalSum // 2 - Define
dfs(i, target):- If
target == 0, returntrue - If
i == len(nums)ortarget < 0, returnfalse - Try both choices:
- Skip
nums[i] - Take
nums[i](reduce target)
- Skip
- If
- Return
dfs(0, target)
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if sum(nums) % 2:
return False
def dfs(i, target):
if i >= len(nums):
return target == 0
if target < 0:
return False
return dfs(i + 1, target) or dfs(i + 1, target - nums[i])
return dfs(0, sum(nums) // 2)Time & Space Complexity
- Time complexity:
- Space complexity:
2. Dynamic Programming (Top-Down)
Intuition
This is the same subset sum idea as the recursive approach, but optimized using memoization.
Key observations:
- If the total sum is odd, we can’t split it into two equal subsets.
- Otherwise, we only need to check if some subset sums to
totalSum / 2.
In plain recursion, many subproblems repeat:
- Same index
i - Same remaining
target
To avoid recomputing them, we store results in a DP table:
memo[i][t]= whether it’s possible to form sumtusing elements from indexionward.
This turns the exponential recursion into a polynomial-time solution.
Algorithm
- Compute
total = sum(nums) - If
totalis odd, returnfalse - Set
target = total // 2 - Create a memo table
memo[n][target + 1]initialized to-1 - Define
dfs(i, target):- If
target == 0, returntrue - If
i == nortarget < 0, returnfalse - If result already exists in
memo, return it - Otherwise:
- Option 1: skip current element →
dfs(i + 1, target) - Option 2: take current element →
dfs(i + 1, target - nums[i]) - Store and return the OR of both choices
- Option 1: skip current element →
- If
- Return
dfs(0, target)
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
n = len(nums)
memo = [[-1] * (target + 1) for _ in range(n + 1)]
def dfs(i, target):
if target == 0:
return True
if i >= n or target < 0:
return False
if memo[i][target] != -1:
return memo[i][target]
memo[i][target] = (dfs(i + 1, target) or
dfs(i + 1, target - nums[i]))
return memo[i][target]
return dfs(0, target)Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the length of the array and is the sum of array elements divided by 2.
3. Dynamic Programming (Bottom-Up)
Intuition
This is a classic 0/1 subset sum DP.
We want to split nums into two subsets with equal sum. That’s only possible if:
total = sum(nums)is even- there exists a subset that sums to
target = total / 2
Instead of trying all subsets (exponential), we build the answer gradually:
- Let
dp[i][j]mean: using the firstinumbers, can we form sumj?
For each number, we have two choices:
- Skip it → the possibility stays
dp[i-1][j] - Take it (only if
nums[i-1] <= j) → checkdp[i-1][j - nums[i-1]]
If either is true, then dp[i][j] is true.
Algorithm
- Compute
total = sum(nums). Iftotalis odd, returnfalse. - Set
target = total // 2,n = len(nums). - Create a DP table
dpof size(n+1) x (target+1)filled withfalse. - Base case:
dp[i][0] = truefor alli(sum0is always achievable by taking nothing). - Fill DP:
- For
ifrom1..n:- For
jfrom1..target:- If
nums[i-1] <= j:dp[i][j] = dp[i-1][j] OR dp[i-1][j - nums[i-1]]
- Else:
dp[i][j] = dp[i-1][j]
- If
- For
- For
- Return
dp[n][target].
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
target = total // 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):
if nums[i - 1] <= j:
dp[i][j] = (dp[i - 1][j] or
dp[i - 1][j - nums[i - 1]])
else:
dp[i][j] = dp[i - 1][j]
return dp[n][target]Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the length of the array and is the sum of array elements divided by 2.
4. Dynamic Programming (Space Optimized)
Intuition
This is the same subset sum idea as before, but optimized to use 1D DP.
Instead of keeping a full 2D table (dp[i][j]), we only track:
dp[j]→ whether sumjis achievable using numbers processed so far
At each number, we build a new state (nextDp) from the previous one:
- Either we don’t take the current number →
dp[j] - Or we take it (if possible) →
dp[j - nums[i]]
This works because each state only depends on the previous row.
Algorithm
- Compute
total = sum(nums). Iftotalis odd, returnfalse. - Set
target = total // 2. - Initialize a boolean array
dpof sizetarget + 1.dp[0] = true(sum0is always possible).
- For each number
numinnums:- Create a new array
nextDp. - For each sum
jfrom1totarget:- If
j >= num:nextDp[j] = dp[j] OR dp[j - num]
- Else:
nextDp[j] = dp[j]
- If
- Replace
dpwithnextDp.
- Create a new array
- Return
dp[target].
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if sum(nums) % 2:
return False
target = sum(nums) // 2
dp = [False] * (target + 1)
nextDp = [False] * (target + 1)
dp[0] = True
for i in range(len(nums)):
for j in range(1, target + 1):
if j >= nums[i]:
nextDp[j] = dp[j] or dp[j - nums[i]]
else:
nextDp[j] = dp[j]
dp, nextDp = nextDp, dp
return dp[target]Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the length of the array and is the sum of array elements divided by 2.
5. Dynamic Programming (Hash Set)
Intuition
This approach also solves Partition Equal Subset Sum, but instead of arrays, it uses a Hash Set to track all achievable sums.
At any point:
dpcontains all subset sums that can be formed using the processed numbers.
For each new number:
- Every existing sum
tcan either:- Stay the same (don’t pick the number)
- Become
t + num(pick the number)
If at any time we form target, we can stop early and return True.
Algorithm
- Compute
total = sum(nums). Iftotalis odd, returnfalse. - Set
target = total // 2. - Initialize a set
dp = {0}(sum0is always possible). - Traverse numbers (order doesn't matter):
- Create an empty set
nextDP. - For each sum
tindp:- If
t + num == target, returntrue. - Add
ttonextDP(skip current number). - Add
t + numtonextDP(take current number).
- If
- Replace
dpwithnextDP.
- Create an empty set
- If loop finishes without finding
target, returnfalse.
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if sum(nums) % 2:
return False
dp = set()
dp.add(0)
target = sum(nums) // 2
for i in range(len(nums) - 1, -1, -1):
nextDP = set()
for t in dp:
if (t + nums[i]) == target:
return True
nextDP.add(t + nums[i])
nextDP.add(t)
dp = nextDP
return FalseTime & Space Complexity
- Time complexity:
- Space complexity:
Where is the length of the array and is the sum of array elements divided by 2.
6. Dynamic Programming (Optimal)
Intuition
This is the most optimal DP solution for Partition Equal Subset Sum.
We reduce the problem to:
Can we pick some numbers whose sum equals
target = total_sum / 2?
We use a 1D DP array where:
dp[j] = Truemeans we can form sumjusing some of the numbers so far.
Key idea:
- For each number, update the DP from right to left so that each number is used only once.
- This avoids overwriting results from the same iteration.
Algorithm
- Compute
total = sum(nums). Iftotalis odd, returnfalse. - Set
target = total // 2. - Create a boolean array
dpof sizetarget + 1.- Initialize
dp[0] = true(sum0is always achievable).
- Initialize
- For each number
numinnums:- Traverse
jfromtargetdown tonum:- Set
dp[j] = dp[j] OR dp[j - num]
- Set
- Traverse
- Return
dp[target].
class Solution:
def canPartition(self, nums: list[int]) -> bool:
if sum(nums) % 2:
return False
target = sum(nums) // 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]Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the length of the array and is the sum of array elements divided by 2.
7. Dynamic Programming (Bitset)
Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the length of the array and is the sum of array elements divided by 2.
Common Pitfalls
Forgetting the Odd Sum Check
The most common mistake is forgetting to check if the total sum is odd before proceeding. If sum(nums) is odd, it's impossible to split into two equal subsets, and you should immediately return false. Skipping this check leads to incorrect results or wasted computation.
Using Left-to-Right Iteration in Space-Optimized DP
When using a 1D DP array, iterating from left to right causes elements to be counted multiple times in the same iteration. You must iterate from right to left (target down to num) to ensure each element is used at most once per subset, preserving the 0/1 knapsack property.
Integer Overflow in Target Calculation
For languages without arbitrary precision integers, the sum of array elements can overflow if not handled carefully. Always use appropriate data types (like long in Java/C++) when computing the total sum before dividing by 2 to get the target.
Sign in to join the discussion