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