<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 {
public:
    int solve(vector <int> &nums, int index, int amount, vector <vector<int>> &dp){
        if(amount < 0) return 0;
        if(amount == 0) return 1;
        if(index<0) return 0;
        if(dp[index][amount]!=-1) return dp[index][amount];
        int a1,a2;
        a1 = solve(nums,index-1, amount, dp);
        a2 = solve(nums, index-1, amount - nums[index], dp);
        return dp[index][amount] = (a1) || (a2);
    }

    bool canPartition(vector<int>& nums) {
        int sum =0;
        for(auto &x:nums) sum += x;
        if(sum&1) return false;
        else{
            sum = sum/2;
            vector <vector<int>> dp(nums.size()+10, vector<int>(sum+100,0));
            // return solve(nums, nums.size()-1, sum/2, dp);
            
            dp[0][0] = 1; dp[0][nums[0]] = 1;
            for(int i=1; i<nums.size(); i++){
                for(int j=0; j<=sum; j++){
                    if(dp[i-1][j]) dp[i][j] = 1;
                    if(j-nums[i]>=0){
                        if(dp[i-1][j-nums[i]]){
                            dp[i][j] = dp[i-1][j-nums[i]];
                        }
                    }
                }
            }
            return dp[nums.size()-1][sum];
        }
    }
};
110899