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.
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 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