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.
My code:
class Solution(object):
#Same code, no TLE
def canPartition1(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
#NP hard problem, no optimizations
nums.sort()
total=sum(nums)
half_sum=int(total/2)
if half_sum*2!=total:
return False
result=self.DFS(nums,0,half_sum)
return result
def DFS1(self,nums,i,target):
if target<0:
return False
if target==0:
return True
if i>=len(nums):
return False
if nums[i]>target:
return False
check_result=self.DFS(nums,i+1,target-nums[i])
if check_result:
return True
check_result=self.DFS(nums,i+1,target)
if check_result:
return True
return False
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
nums.sort(reverse=True)
if sum(nums) & 1:
return False
return self.dfs(0, nums, sum(nums) >> 1)
def dfs(self, i, nums, target):
if nums[i] == target:
return True
if nums[i] > target:
return False
if i + 1 == len(nums):
return False
return self.dfs(i+1, nums, target - nums[i]) or self.dfs(i+1, nums, target)
Solution: https://leetcode.com/problems/partition-equal-subset-sum/