How Do You Solve Partition Equal Subset Sum?
Learn how partition equal subset sum reduces to subset sum, its DP solution, and how to answer this interview question well.
Expected Interview Answer
Partition equal subset sum asks whether an array can be split into two subsets with equal totals, which is only possible if the overall sum is even, and then reduces exactly to a subset sum problem: can some subset reach half of the total, solved in O(n*sum/2) time with a boolean DP.
First compute the total sum; if it is odd, an equal split is immediately impossible since two equal integer subsets can never sum to an odd total. If the sum is even, the target becomes sum/2, and the question becomes identical to subset sum: does some subset of the array reach exactly that target? The same include/exclude boolean DP applies — dp[s] is true if s is reachable using items considered so far — and if dp[target] ends true, one subset reaching target automatically leaves the remaining elements summing to the other equal half. This reduction is the key interview insight: recognizing the problem collapses to a well-known subproblem rather than needing new machinery.
- Reduces directly to the well-understood subset sum problem
- Early odd-sum check prunes impossible cases in O(n)
- O(n * sum/2) time is efficient for reasonable value ranges
- The complement subset is free once the target subset is found
AI Mentor Explanation
A tournament organizer wants to split a set of teams into two divisions with exactly equal combined win totals. If the grand total of all wins across every team is odd, an even split is impossible immediately, since two equal halves can never add to an odd number. If the total is even, the question becomes whether some subset of teams can be selected whose wins sum to exactly half the total — solved the same way as any reachable-sum problem, checking each team once. If such a subset exists, the leftover teams automatically form the other equal-win division, so only one subset needs to be found, not two.
Step-by-Step Explanation
Step 1
Check the total sum parity
Compute sum(nums); if it is odd, immediately return false — an equal split is impossible.
Step 2
Set the target
If sum is even, the target for one subset is sum // 2.
Step 3
Run subset sum DP
Use a boolean dp array of size target+1, updated for each number in reverse sum order to avoid reuse.
Step 4
Return dp[target]
If target is reachable, the remaining elements automatically form the other equal-sum subset.
What Interviewer Expects
- Recognize the odd-sum early exit before any DP work
- Correctly reduce the problem to subset sum with target = sum / 2
- State time complexity O(n * sum/2) and explain the reverse-order 1D iteration
- Explain why finding one matching subset guarantees the complement matches too
Common Mistakes
- Forgetting to check for odd total sum before running the DP
- Using sum instead of sum // 2 as the DP target
- Iterating sums forward instead of backward in the 1D optimization, allowing reuse of an element
- Not realizing this problem is just subset sum in disguise and reimplementing from scratch inefficiently
Best Answer (HR Friendly)
“This problem is really subset sum wearing a different costume: I first check if the total is even, because two equal halves can never add to an odd number, and if it's even I just ask 'can some subset hit exactly half the total', since whatever is left over automatically balances the other half.”
Code Example
def can_partition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for s in range(target, num - 1, -1):
if dp[s - num]:
dp[s] = True
if dp[target]:
return True
return dp[target]
# Example
print(can_partition([1, 5, 11, 5])) # True: [1, 5, 5] and [11]Follow-up Questions
- Why does the algorithm return false immediately for an odd total sum?
- How does this problem reduce exactly to the subset sum problem?
- How would you extend this to partition into k equal-sum subsets instead of 2?
- How would you reconstruct the actual two subsets, not just answer true/false?
MCQ Practice
1. What is the first check performed before running the DP in partition equal subset sum?
An odd total sum can never split into two equal integer halves, so it is checked and rejected before any DP work.
2. If the total sum is even, what target does the subset sum DP search for?
The problem reduces to finding whether a subset reaches exactly half the total, since the remainder automatically forms the other equal half.
3. What is the time complexity of the partition equal subset sum solution for n numbers with total sum S?
It runs the standard subset sum DP with target S/2, giving O(n * S/2) time, the same pseudo-polynomial bound as subset sum.
Flash Cards
When is an equal-sum partition immediately impossible? — When the total sum of the array is odd.
What does partition equal subset sum reduce to? — Subset sum with target equal to half the total sum.
Why is only one subset search needed, not two? — If one subset reaches the target, the remaining elements automatically sum to the other equal half.
What is the time complexity of the solution? — O(n * sum/2), the same pseudo-polynomial bound as the underlying subset sum DP.