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

• 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)
``````

• 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]

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