Partition Equal Subset Sum
You get an array nums of positive integers. Decide whether you can split the values into two groups whose sums are equal. Every value goes into exactly one group, and a group can take values from any positions. Return true if such a split exists and false otherwise.
Function
- numsinteger-array
- the positive values to split into two groups
- Returnsboolean
- true when the values can form two groups with equal sums, false otherwise
Constraints
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 100
Examples
- Input
- nums = [6, 1, 4, 9, 2]
- Output
- true
- Explanation
- The total is 22, so each group needs 11. The groups 9 + 2 and 6 + 1 + 4 both make 11, so the answer is
true.
- Input
- nums = [4, 7, 2, 9, 6]
- Output
- false
- Explanation
- The total is 28, so each group needs 14. The group that holds 9 needs 5 more, and no mix of 4, 7, 2 and 6 makes 5, so the answer is
falseeven though the total is even.
- Input
- nums = [1, 2, 3, 5]
- Output
- false
- Explanation
- The total is 11. Two equal whole numbers always add up to an even number, so an odd total can never be split and the answer is
false.
Follow-up
When no equal split exists, can you return the smallest possible difference between the two group sums?
Hints
Open them one at a time. Each one gives away a little more.
If the two groups have equal sums, what must each sum be, in terms of the total of
nums? And what does an odd total tell you right away?You only need to find one group that adds up to half the total; the values left over form the other group. Think about the set of sums the first few values can reach, and how one more value changes that set.
Keep a boolean array
reach[0..target]with onlyreach[0]true. For each valuenum, walksfromtargetdown tonumand markreach[s]whenreach[s-num]is marked. Walking down keeps each value from being used twice.
Solution
Each group must hold half the total, so the question becomes: does some subset of nums add up to target = total / 2? Trying every subset costs 2^n. The sums are small, though, at most 200 × 100 / 2 = 10^4, so a 0/1 knapsack table of reachable sums answers it in O(n × target) steps.
Try every subset with recursion
Correct, but does not finish on the largest tests
Intuition
If the total is odd, no split exists. Otherwise pick values for the first group until they make target; the values left over make the other half on their own. A helper reach(i, remaining) decides each value in turn: take nums[i] or leave it.
Every subset is one path of choices, so the search cannot miss a split. An input with no split forces it through almost every path, up to 2^n: about 10^12 for n = 40 and 1.6 × 10^60 for n = 200.
Algorithm
- Add up
nums. If the total is odd, returnfalse. - Set
targetto half the total. - Write
reach(i, remaining): return true whenremainingis 0, and false wheniis past the last value orremainingis below 0. - Otherwise return
reach(i+1, remaining-nums[i])orreach(i+1, remaining): take the value or leave it. - Return
reach(0, target).
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
# Can some of the values from index i on add up to exactly remaining?
def reach(i, remaining):
if remaining == 0:
return True
if i == len(nums) or remaining < 0:
return False
# Put nums[i] in the first group, or leave it for the second one
return reach(i + 1, remaining - nums[i]) or reach(i + 1, remaining)
return reach(0, total // 2)Fill a table by value and sum
Intuition
reach(i, remaining) depends on two numbers only, so there are at most (n+1) × (target+1) different questions, about 201 × 10001 ≈ 2 × 10^6. Answer each once in a table: can[i][s] says whether some of the first i values add up to s. Row 0 is false except can[0][0].
The value num = nums[i-1] either stays out, so the earlier values already reach s, or goes in, so they reach s-num. Each row reads only the row above, so every value is used at most once. In the first example the reachable sums grow from {0} to {0, 6}, {0, 1, 6, 7}, then {0, 1, 4, 5, 6, 7, 10, 11}: 6 + 1 + 4 reaches 11.
Algorithm
- Return
falsefor an odd total and settargetto half of it. - Make a table with n+1 rows and target+1 columns, all false, and set
can[0][0]to true. - For each row
ifrom 1 to n, takenum = nums[i-1]. - For each sum
sfrom 0 totarget, setcan[i][s]tocan[i-1][s]or, whens ≥ num,can[i-1][s-num]. - Return
can[n][target].
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
target = total // 2
n = len(nums)
# can[i][s] is True when some of the first i values add up to s
can = [[False] * (target + 1) for _ in range(n + 1)]
can[0][0] = True
for i in range(1, n + 1):
num = nums[i - 1]
for s in range(target + 1):
# Leave num out, or put it in and reach s - num with the values before it
can[i][s] = can[i - 1][s] or (s >= num and can[i - 1][s - num])
return can[n][target]One row of sums, filled from the top down
Intuition
Each row reads only the row above, so keep one row reach and update it in place. The order of updates matters. Walking s upward reads sums this same value already switched on: in the first example the 1 would mark sum 1, then read it to mark 2, then 3, as if you owned many 1s.
Walk s downward from target to num. Then s-num is an index this value has not touched, so reach[s-num] still equals can[i-1][s-num]. You can stop once reach[target] is true, since later values never remove a sum. The time stays O(n × target) and the memory drops to target + 1 booleans.
Algorithm
- Return
falsefor an odd total and settargetto half of it. - Make
reachwithtarget + 1entries, all false exceptreach[0]. - For each value
num, walksfromtargetdown tonumand setreach[s]to true whenreach[s-num]is true. - After each value, return
trueifreach[target]is true. - If the loop ends, return
reach[target], which is false.
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
target = total // 2
# reach[s] is True when some of the values seen so far add up to s
reach = [False] * (target + 1)
reach[0] = True
for num in nums:
# Walk the sums downward so num is used at most once
for s in range(target, num - 1, -1):
if reach[s - num]:
reach[s] = True
if reach[target]:
return True
return reach[target]
Pitfalls and edge cases
- Walking the sums upward in the one-row version. With
[3, 9]and target 6, the 3 marks sum 3 and then sum 6, and you answer true. - Skipping the odd check. For
[1, 2]the total 3 rounds down to a target of 1, the value 1 reaches it, and you answer true. - Adding each value to the lighter group. On
[3, 3, 2, 2, 2]that ends at 7 against 5, while 3 + 3 = 2 + 2 + 2. - Not skipping a value larger than the target, as in
[2, 2, 2, 10]. In R a range such as(num+1):(target+1)then counts backward and breaks the loop. - Reading sum
sat indexsin Lua or R, where it sits ats + 1.
Frequently asked questions3
Why is Partition Equal Subset Sum a 0/1 knapsack problem?
You fill a knapsack of size target = total / 2 exactly, using each value at most once. Taking or leaving a value is the 0/1 choice, and a value's size is the value itself. The table of reachable sums answers it in O(n × target) time.
What is the time complexity of Partition Equal Subset Sum?
O(n × target) time, where target is half the total, and O(target) memory with one row: about 2 × 10^6 steps for 200 values of at most 100. The bound grows with the size of the values, so it is pseudo-polynomial; the general problem is NP-complete.
Can Partition Equal Subset Sum be solved with a bitset?
Yes. Store the reachable sums as the bits of one large number, starting with bit 0 set. For each value, bits |= bits << num adds it to every reachable sum at once, and the answer is bit target. It is the same table, with 64 sums per machine word.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def canPartition(nums):
# Write code hereTest #1
Test #2
Test #3
Argument
nums = [6, 1, 4, 9, 2]
Expected Output
true