PROBLEM STATEMENT
We are given array, we need to find if it is possible to divide the array in two subsets such that the sum of the subsets are equal.
QUICK POINTS:
1. We need to divide the array in two parts such that the sum of the two parts is equal. So, It is clear that the total sum of the array should be an even number, otherwise we can't divide it in equal parts and the sum of each of the two subsets should be equal to half of the total sum.
sum of each subset= (total sum)/2;
2. Now, you can obviously guess it that we only need to find if there exists any subset in the array whose sum is equal to half of the total sum. The sum of the rest of the elements will also be equal to half of the total sum. The reduced solution is similar to
3. Now, for each element of the array, we will check if we will take the element or not as discussed below.
STEPS INVOLVED:
1. We are taking n, the size of array and the array a[n] as user input.
2. Then, we are calculating total sum. If the sum is not divisible by 2 i.e not even, the we are directly concluding that the partition is not possible. If even, then sum of each subset subsetsum will be sum/2.
3. If the is even, i.e. divisible by 2, then we are taking a matrix table to analysis each and every condition starting from subsetsum=0 and taking zero element. The matrix is of size (n+1)*(subsetsum+1).
4. If the subsetsum=0, i,e. j=0, in the code, the output will be true. Also, if we don't take any element i.e. i=0, and j!=0 then the output will be false. These are the initial conditions.
5. if the element we have taken is greater than subset sum, then we will just exclude that element and will return the output state as the previous state.
6. If the element is less than or equal to current subsetsum, then we will either take the element or will not take the element, the output will depend on previous state.
CODE:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int sum=0;
for(int i=0;i<n;i++)
sum=sum+a[i];
if(sum%2!=0)
cout<<"NO";
else
{
int p=sum/2;
bool dp[n+1][p+1];
for(int i=0;i<n+1;i++)
{
for(int j=0;j<p+1;j++)
{
if(j==0)
dp[i][j]=true; //initialization
else if(i==0)
dp[i][j]=false; //initialization
else if(a[i-1]<=j)
dp[i][j]=(dp[i-1][j-a[i-1]])|| dp[i-1][j]; //choosing if we will take current element
else if(a[i-1]>j)
dp[i][j]=dp[i-1][j]; //if the current element is greater than sum then, we will not take
}
}
if(dp[n][p]==1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
0 Comments