<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:
    @cache
    def bottom_up(self, nums):
        # print(dp)
        index = len(nums)
        dp = [[False]*(self.needed_sum+1) for _ in range(index+1)]
        for i in range(len(nums)):
            dp[i][0] = True
        for i in range(1, len(nums)+1):
            for current_sum in range(1, self.needed_sum+1):
                if current_sum < nums[i-1]:
                    dp[i][current_sum] = dp[i-1][current_sum]
                else:
                    dp[i][current_sum] = dp[i-1][current_sum] or dp[i -
                                                                    1][current_sum-nums[i-1]]
        return dp[index][self.needed_sum]

    def top_down(self, nums, index, current_sum):
        # print(dp)
        if index < 0 or current_sum > self.needed_sum:
            return False
        if self.dp[index][current_sum]:
            return self.dp[index][current_sum]
        if current_sum == self.needed_sum:
            return True
        sum1 = self.bottom_up(
            nums=nums, index=index-1, current_sum=current_sum+nums[index])
        sum2 = self.bottom_up(
            nums=nums, index=index-1, current_sum=current_sum)
        if sum1:
            self.dp[index][current_sum] = sum1
        else:
            self.dp[index][current_sum] = sum2
        return self.dp[index][current_sum]

    # def recursion(self, nums, index, needed_sum):
    #     if index < 0:
    #         return False
    #     if needed_sum == 0:
    #         return True
    #     sum1 = self.recursion(
    #         nums=nums, index=index-1, needed_sum=needed_sum-nums[index])
    #     sum2 = self.recursion(
    #         nums=nums, index=index-1, needed_sum=needed_sum)
    #     if sum1:
    #         return sum1
    #     return sum2

    def canPartition(self, nums) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return False
        self.needed_sum = total_sum//2
        index = len(nums)
        self.dp = [[False]*(self.needed_sum+1) for _ in range(index)]

        # res = self.recursion(nums=nums, index=len(nums) -
        #  1, needed_sum=total_sum/2)
        # print(res)
        # return res
        # res = self.top_down(nums=nums, index=len(nums)-1,
        # current_sum=0)
        res = self.bottom_up(tuple(nums))
        print(res)
        return res


# sol = Solution()
# sol.canPartition(nums=[1, 5, 11, 5])

168020