# 416. Partition Equal Subset Sum
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
# Solution
Approach 1: recursion/backtracking.
Approach 2: DP using a 2D array.
# Code (Python)
Approach 1:
def canPartition1(self, nums: List[int]) -> bool:
total = sum(nums)
if sum(nums) % 2 == 1 or len(nums) == 1 or max(nums) > total / 2:
return False
nums.sort(reverse=True) # trick to glob the bigger chunks early
# recursion/backtracking
return self._can_sum_to(0, nums, total / 2)
def _can_sum_to(self, start, nums, total):
if start >= len(nums) or total < 0: # where nums[start] > total is not a False condition because the following nums are less than nums[start]
return False
elif nums[start] == total or total == 0:
return True
new_start = start + 1 # careful for new_start out of index range
while new_start < len(nums) and nums[new_start] == nums[start]:
new_start += 1
return (self._can_sum_to(start + 1, nums, total - nums[start]) or
self._can_sum_to(new_start, nums, total))
Approach 2:
def canPartition(self, nums):
# DP: LTE for a single test case but otherwise it should work
total = sum(nums)
if sum(nums) % 2 == 1 or len(nums) == 1 or max(nums) > total / 2:
return False
nums.sort(reverse=True)
# can_do[i][j] -- nums[:i+1] contains a subset that sums up to j
# transfer: can_do[i][j] = can_do[i-1][j] or can_do[i-1][j-nums[i]]
can_do = [[False for j in range(total // 2 + 1)] for i in range(len(nums))]
for i in range(len(nums)):
can_do[i][0] == True
for j in range(total // 2 + 1):
if i == 0:
can_do[0][j] = (nums[0] == j or j == 0)
else:
can_do[i][j] = can_do[i-1][j]
if j - nums[i] >= 0:
can_do[i][j] = can_do[i][j] or can_do[i-1][j-nums[i]]
return can_do[-1][-1]
# Code (C++)
Approach 1:
Approach 2: