416. Partition Equal Subset Sum

Medium

---

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

• 1 <= nums.length <= 200

• 1 <= nums[i] <= 100

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        target = total // 2
        if total%2 == 1 or len(nums) == 1:
            return False
        d = {}
        def recursion(target, index, d):
            if target < 0 or index == len(nums):
                return False
            elif target == 0:
                return True
            elif (index, target) in d:
                return d[(index, target)]
            value = recursion(target - nums[index], index+1, d) or recursion(target, index+1, d)
            d[(index, target)] = value
            return value
        return recursion(target, 0, d)