Description
Decide whether positive integers can be split into two subsets of equal total. Each element belongs to exactly one subset.
Solution
def can_partition(nums):
total = sum(nums)
if total % 2:
return False
target = total // 2
possible = [False] * (target + 1)
possible[0] = True
for value in nums:
for amount in range(target, value - 1, -1):
possible[amount] = possible[amount] or possible[amount - value]
return possible[target]Examples
Example 1
- Input
[[1,5,11,5]]- Output
true
11 equals 1 + 5 + 5.
Example 2
- Input
[[1,2,3,5]]- Output
false
The total is odd.
Example 3
- Input
[[2,2]]- Output
true
Each subset contains one 2.
Approach
An odd total is impossible. Otherwise use a one-dimensional subset-sum table for half the total. Process each number and update reachable sums downward so that number is used at most once.
Time & space
O(n S) time and O(S) auxiliary space, where n is element count and S is half the total.