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.

Difficulty: interview

Starter code:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        

Solutions:
class Solution:
     def canPartition(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         _sum=sum(nums)
         div,mod=divmod(_sum,2)
         if mod!=0:
             return False
         target=[div]*2
         self._len=len(nums)
         nums.sort(reverse=True)
         def dfs(index,target):
             if index==self._len:
                 return True
             num=nums[index]
             for i in range(2):
                 if target[i]>=num:
                     target[i]-=num
                     if dfs(index+1,target):return True
                     target[i]+=num
             return False
         return dfs(0,target)
             
         
         


class Solution:
     def canPartition(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         _sum = sum(nums)
         div, mod = divmod(_sum, 2)
         if mod or max(nums) > div: return False
         nums.sort(reverse = True)
         target = [div] * 2
         return self.dfs(nums, 0, target)
     
     def dfs(self, nums, index, target):
         for i in range(2):
             if target[i] >= nums[index]:
                 target[i] -= nums[index]
                 if target[i] == 0 or self.dfs(nums, index + 1, target): return True
                 target[i] += nums[index]
         return False

class Solution:
     def canPartition(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         nums.sort( reverse=True)
         print(nums)
         numsum = sum(nums)
         if numsum %2 != 0:
             return False
         halfsum = numsum //2
         t_sum = nums[0]
         if t_sum >halfsum:
             return False
         elif t_sum == halfsum:
             return True
 
         llen = len(nums) 
         for startpos in range(1,llen):
             curpos = startpos
             while t_sum<halfsum and curpos < llen:
                 if (t_sum+nums[curpos]>halfsum):
                     curpos += 1
                 elif (t_sum+nums[curpos]==halfsum):
                     #print(curpos, t_sum,len(nums))
                     return True
                 else:
                     t_sum += nums[curpos]
                     curpos += 1
                 pass
             t_sum=nums[0]
         return False

class Solution:
     def search(self, nums, pos, target, seen):
         if (pos, target) in seen:
             return False
         if target == 0:
             return True
         if pos >= len(nums) or nums[pos] > target:
             return False
         if self.search(nums, pos + 1, target - nums[pos], seen):
             return True
         if self.search(nums, pos + 1, target, seen):
             return True
         seen.add((pos, target))
         return False
         
     def canPartition(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         s = sum(nums)
         if s % 2 == 1:
             return False
         target = s // 2
         nums = sorted(nums)
         return self.search(nums, 0, target, set())


class Solution:
     def canPartition(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         
         if len(nums) < 2:
             return False
         
         s = sum(nums)
         if s % 2 != 0:
             return False
         
         s = s // 2
         nums.sort()
         mem = dict()
         
         return self.dp(nums, 0, s, mem)
     
     def dp(self, nums, start, s, mem):
         
         if s == 0:
             return True
         
         if start >= len(nums):
             return False
         
         state = mem.get((start, s), None)
         if state is not None:
             return state
         
         res = False
         if nums[start] > s:
             res = False
             
         else:
             res = self.dp(nums, start+1, s-nums[start], mem) or self.dp(nums, start+1, s, mem)
             
         mem[(start, s)] = res
         return res

class Solution:
     def canPartition(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         sum_ = sum(nums)
         if sum_%2 == 0:
             target = sum_/2
             def myFun(t,nu):
                 nu.sort()
                 nu.reverse()
                 for index,item in enumerate(nu):
                     if item == t:
                         return True
                     elif item > t:
                         return False
                     else:
                         nun = nu.copy()
                         del nun[index]
                         if myFun(t-item,nun):
                             return True
                         elif index == len(nu)-1:
                             return False
             return myFun(target,nums)
         return False


class Solution:
     def canPartition(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         s = 0
         bits = 1
 
         for num in nums:
             s += num
             bits |= bits << num
 
         return not (s & 1) and ((bits >> (s >> 1)) & 1) == 1


class Solution:
     def canPartition(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         '''
         sums = sum(nums)
         if sums & 1:
             return False
         target = sums//2
         if max(nums) > target:
             return False
         elif max(nums) == target:
             return True
         target -= max(nums)
         nums = [num for num in nums if num <= target]
         if not nums:
             return False
         if target in nums:
             return True
         pool = set([0])
         for num in nums:
             for p in pool.copy():
                 pool.add(num+p)
         return target in pool
         '''
         '''
         s = sum(nums)
         if s & 1:
             return False
         target = s//2
         pool = set([0])
         for num in nums:
             for p in pool.copy():
                 pool.add(num+p)
         return target in pool
         '''
         s = sum(nums)
         if s & 1:
             return False
         target = s//2
         cnt = collections.Counter(nums)
         return self.helper(target, cnt)
         
     def helper(self, target, cnt):
         if target == 0:
             return True
         if target < 0:
             return False
         for item in sorted(list(cnt.keys()), reverse=True):
             if cnt[item] == 0:
                 continue
             cnt[item] -= 1
             if self.helper(target-item, cnt):
                 return True
             cnt[item] += 1
         return False


class Solution:
     def canPartition(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         target=sum(nums)
         if target % 2==1: return False
         target=target//2
         if any([x for x in nums if x>target]): return False
         nums.sort()
         def check(nums,target):
             if target in nums:
                 return True
             if (not nums) or (nums[0]>target):
                 return False
             res=False
             tag="@"
             for i in range(len(nums)):
                 if tag!=nums[i]:
                     tag=nums[i]
                     res=res|check(nums[:i]+nums[i+1:],target-nums[i])
                     if res:return True
             return res
         return check(nums,target)