**Solution**

**Partition Equal Subset Sum** https://leetcode.com/problems/partition-equal-subset-sum/

**Algorithm**

- If the sum of all elements is odd, then you cannot have 2 subsets with equal sum. So test this and return False.
- If the sum is even, then the problem produces to find a subset which is equal to a target sum.
- is_subset(i, target) = Can we form target using array[i,...N-1]?
- You can include nums[i] or exclude nums[i] and reduce the problem to the nums array starting from i+1.
- is_subset(i, target) = is_subset(i+1, target) or is_subset(i+1, target-nums[i])

```
from collections import defaultdict
class Solution(object):
def helper(self, i, array, target, cache):
if target == 0:
return True
elif target < 0 or i == len(array):
return False
else:
if i in cache and target in cache[i]:
return cache[i][target]
else:
cache[i][target] = self.helper(i+1, array, target, cache)
if target-array[i] >= 0:
cache[i][target] = cache[i][target] or self.helper(i+1, array, target-array[i], cache)
return cache[i][target]
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
total = sum(nums)
if total & 1:
return False
else:
target = total // 2
return self.helper(0, nums, target, defaultdict(dict))
```