<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:
    bool checkSum(vector<int>&nums,int ind,int target,vector<vector<int>>&dp){
        if(target == 0) return true;
        if(ind==0) return (nums[ind]==target);
        if(dp[ind][target]!=-1) return dp[ind][target];
        bool notTake = checkSum(nums,ind-1,target,dp);
        bool take = false;
        if(nums[ind]<=target) take = checkSum(nums,ind-1,target-nums[ind],dp);
        return dp[ind][target] = take|notTake;
    }

    bool checkSumTabulation(vector<int>&nums,int target,int n){
        vector<vector<bool>>dpt(n,vector<bool>(target+1,0));
        for(int i = 0;i<n;i++) dpt[i][0] = true;
        if(nums[0]<=target) dpt[0][nums[0]] = true;

        for(int i = 1;i<n;i++){
            for(int j = 1;j<=target;j++){
                bool notTake = dpt[i-1][j];
                bool take = false;
                if(j>=nums[i]) take = dpt[i-1][j-nums[i]];
                dpt[i][j] = take | notTake;
            }
        }
        return dpt[n-1][target];
    }

    bool checkSumOptimized(vector<int>&nums,int target,int n){
        vector<bool> prev(target+1,0);
        prev[0] = true;
        if(nums[0]<=target) prev[nums[0]] =true;
        for(int i = 1;i<n;i++){
            vector<bool> curr(target+1,0);
            curr[0]=true;
            for(int j = 1;j<=target;j++){
                bool notTake = prev[j];
                bool take = false;
                if(j>=nums[i]) take = prev[j-nums[i]];
                curr[j] = take|notTake;
            }
            prev = curr;
        }
        return prev[target];
    }
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for(int i = 0;i<n;i++){
            sum += nums[i];
        }
        int target = sum/2;
        vector<vector<int>> dp(n,vector<int>((sum/2)+1,-1));
        if(sum%2==1) return false;
        else{
            //return checkSum(nums,n-1,target,dp);
            //return checkSumTabulation(nums,target,n);
            return checkSumOptimized(nums,target,n);      
        }

    }
};
130945