Simple python solution with list and array


  • 0
    H
    class Solution(object):
        def canPartition(self, nums):
            total = sum(nums)
            target = total >> 1
            
            if total & 1 == 1:
                return False
                
            pos_list = [0]
            pos_array = [True] + [False] * total
            
            for num in nums:
                l = len(pos_list)
                for i in xrange(l):
                    cur = num + pos_list[i]
                    
                    if cur == target:
                        return True
                    elif cur < target and pos_array[cur]==False:
                        pos_array[cur]=True
                        pos_list.append(cur)
            return False
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.