<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>

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fr(i,n) for(ll i=0;i<(n);++i)
#define fr1(i,n) for(ll i=1;i<=(n);++i)


ll n;
ll dp[205][20005];
ll a[205];
ll pref[205];
ll rec(ll i,ll s1,ll s2){
    // pr(i,s1,s2,a[i],pref[i]);
 if(i==n){
    // pr(s1,s2);
    return ((s1==s2) && s1!=0 && s2!=0);
 }
 if(dp[i][s1]!=-1){
    return dp[i][s1];
 }
 ll ans=0;

 if(rec(i+1,s1+a[i],s2)==1){
     ans=1;
 }
 if(rec(i+1,s1,s2+a[i])==1){
    ans=1;
 }
 return dp[i][s1]=ans;
}
class Solution {
public:
    bool canPartition(vector<int>& b) {
        n=(ll)b.size();
	ll sm=0;
	fr(i,n){
		a[i]=b[i];
		 sm+=a[i];
// 		 pref[i]=0;
//  if(i) pref[i]+=(pref[i-1]+a[i]);
//  else pref[i]=a[i];
	}
	fr(i,n+1){
    fr(j,sm+1){
        dp[i][j]=-1;
    }
}
return rec(0,0,0);

    }
};
45033