PROBLEM STATEMENT:
We are given an array, We have to divide the array in two parts such that the absolute difference between the sum of the two parts is minimum possible.
QUICK POINTS:
1. When there is no element in the array, the difference is 0.
2. The range of the difference will be from 0 to total sum of the array.
STEPS:
1. We are taking an array a of size n as input.
2. Now, we will find the total sum of the array which is range of the difference i.e. difference may vary from 0 to total sum. If s is the sum of one partition, then total sum-s is the sum of other part and | sum-s-s| should be minimum, so it can be concluded that we have to find minimum value of |sum-2*s|.
3. So, now the problem can be derived from subset sum problem, we are to find all the sums from 0 to total sum which are possible in the array, i.e. the sums that can be possible by taking any subset from the array.
4. We are taking a boolean matrix of size (n+1)*(sum+1) which will give us if the sum is possible. If we are not taking any element and sum is not equal to zero, the value of matrix will be false. If sum is zero, value will be true always.
5. If the element is greater than the current sum (j) we will not include the element.
6. If the element is less than current sum (j), then we can either include the element or exclude the element.
7. Now, to find the minimum difference, we have to take the maximum current sum starting from (total sum)/2, that is possible in the array, i.e. dp[n][current sum]= true, and we will subtract 2*current sum from total sum, i.e. |sum-2*j|, j is the current sum.
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];
bool dp[n+1][sum+1];
for(int i=0;i<n+1;i++)
{
for(int j=0;j<sum+1;j++)
{
if(j==0)
dp[i][j]=1;
else if(i==0)
dp[i][j]=0;
else
{
if(a[i-1]<=j)
dp[i][j]=dp[i-1][j]|| dp[i-1][j-a[i-1]];
else
dp[i][j]=dp[i-1][j];
}
}
}
int d;
for(int j=sum/2;j>=0;j--)
{
if(dp[n][j]==true)
{
d=sum-2*j;
break;
}
}
cout<<d<<endl;
return 0;
}
0 Comments