<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 canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        sum_nums = sum(nums)
        
        if sum_nums % 2 == 1:
            return False
        
        target = sum_nums / 2
        
        # (i, rem) -> bool
        memo = {}
        
        def recurse(i: int, remaining:int) -> bool:
            if i == n:
                if remaining == 0:
                    return True
                return False
            
            if remaining < 0:
                return False
            
            if (i, remaining) in memo:
                return memo[(i, remaining)]
            
            num = nums[i]
            
            memo[(i, remaining)] = (recurse(i + 1, remaining) or
                                       recurse(i + 1, remaining - num))
            
            return memo[(i, remaining)]
        
        return recurse(0, target)
        
        
        

"""
if sum(nums) == odd -> return False (if only integer inputs)

include/exclude at each num -> 0/1 knapsack problem

target: t = sum(nums) / 2
n = len(nums)
subproblem: p(i, x) = whether we can reach the target x in nums[i:]
recurrence relation: p(i, x) = OR{p(i + 1, x), p(i + 1, x - nums[i])}
decreasing in i, increasing in x (0, t)
base case: p(n, x) = False if x != 0 else True
original problem: p(0, t)
tc: O(n * t) -> pseudopolynomial
sc: O(n * t)
"""
489523