Python super fast solution (55ms), beats 96%


  • 0
    Y

    The below algorithm try to put each element into two subsets, so it should be power(2,n) complexity. With simple prune strategy, the search space seems to be greatly reduced.

    class Solution(object):
        def canPartition(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            if not nums or sum(nums)%2==1: return False
            half = sum(nums)/2
            nums.sort()
            base = nums[-1]
            if base>half: return False
            if base==half: return True
            return self.partition(nums[:-1],half-base,half)
            
        def partition(self,arr,target1,target2):
            if target1==0 or target2==0: return True
            if not arr or target1<0 or target2<0: return False
            enum = arr[-1]
            if enum>target1:
                return self.partition(arr[:-1],target1,target2-enum)
            if enum>target2:
                return self.partition(arr[:-1],target1-enum,target2)
            return self.partition(arr[:-1],target1,target2-enum) or self.partition(arr[:-1],target1-enum,target2)
    

  • 0
    Y

    The above algorithm is still 2^n, so should be very slow. I believe the test case is not well designed to show the behavior.

    Adding a test case like below will substantially reduce the performance:
    nums=[2, 6, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99]


Log in to reply
 

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