Partition Equal Subset Sum

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

SOLUTION:

class Solution:
    def isSubsetSum(self, arr, total, n):
        if total == 0:
            return True
        if total != 0 and n == 0:
            return False
        if (n, total) in self.cache:
            return self.cache[(n, total)]
        if 2 * arr[n - 1] > total:
            return self.isSubsetSum(arr, total, n - 1)
        self.cache[(n, total)] = self.isSubsetSum(arr, total, n - 1) or self.isSubsetSum(arr, total - 2 * arr[n - 1], n - 1)
        return self.cache[(n, total)]

    def canPartition(self, nums: List[int]) -> bool:
        self.cache = {}
        n = len(nums)
        total = sum(nums)
        if total % 2 == 1:
            return False
        return self.isSubsetSum(nums, total, n)