<p>Given an integer array <code>nums</code>, return <code>true</code> <em>if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or </em><code>false</code><em> otherwise</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 200</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 100</code></li>
</ul>

class Solution:
    def __init__(self):
        self.mapping = {}

    def canPartition(self, nums: List[int]) -> bool:
        n = sum(nums)
        if n % 2 == 1:
            return False
        return self.solve(nums, n//2, 0, 0)

    def solve(self, nums, target, val, pos):
        if target == 0:
            return True
        elif pos == len(nums):
            return False
        val = str(target)+'-'+str(pos)
        if val in self.mapping:
            return self.mapping[val]
        if nums[pos] <= target:
            ans = (self.solve(nums, target-nums[pos], val, pos+1) or 
            self.solve(nums, target, val, pos+1))
        else:
            ans = self.solve(nums, target, val, pos+1)
        self.mapping[val] = ans
        return ans
126344