equal sum partition
#include <bits/stdc++.h>
using namespace std;
bool subsetsum(vector<int>&vec,int sum,int n)
{
bool dp[n+1][sum+1];
for(int i=0;i<=n;i++)
{
for(int j=0;j<=sum;j++)
{
if(i==0)
{
dp[i][j]=false;
}
if(j==0)
{
dp[i][j]=true;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=sum;j++)
{
if(vec[i-1]<=j)
{
dp[i][j]=(dp[i-1][j-vec[i-1]])||(dp[i-1][j]);
}
else
{
dp[i][j]=dp[i-1][j];
}
}
}
return dp[n][sum];
}
bool sumpart(vector<int>&vec,int n)
{
int sum=accumulate(vec.begin(),vec.end(),0);
if(sum&1)
{
return false;
}
else
{
return subsetsum(vec,sum/2,n);
}
}
int main()
{
int n;
cin>>n;
vector<int>vec(n);
for(int i=0;i<n;i++)
{
cin>>vec[i];
}
cout<<sumpart(vec,n);
return 0;
}