PROBLEM STATEMENT:
We are given an array and a sum, we can assign a sign to each element of the array, either positive or negative so that the sum of the array becomes equal to the given sum. We have to find number of such combinations.
QUICK POINTS:
1. Here, we can see that if we assign +ve sign to some element and -ve sign to some other elements, then the sum of these two subsets is actually the difference of the two subsets in the actual problem( -ve sign is taken common from all -ve elements).
2. Basically, we have to determine the number of subsets with given difference, here, the given difference is equal to the given sum.
Difference= sum
1. Let's take actsum be the subset of one subset, totalsum be the total sum of the array and diff be the given difference which is equal to given sum.
It is obvious that
actsum-(totalsum-actsum)=diff
=> 2*actsum= diff+ totalsum
=> actsum= (diff+totalsum)/2;
So, simply we can get the answer by finding the number of subsets with given sum= actsum, which is same as subset sum problem.
STEPS:
1. We are taking user input n, sum, a[n] as size of array, given sum and the array respectively.
2. Now, we can find actsum=(totalsum + sum)/2
2. Now, we are taking a matrix of size (n+1)*(actsum+1) to store the count for each cases smaller than the given case, to recursively get the value of the given case.
3. Now, we are using two loops for the matrix, i is for size of array and j is for current sum. You can initialize that if sum is zero i.e. j=0, count will be 1 and if size is zero and sum is not equal to zero, i.e. i=0 and j!=0, the count will be zero.
4. In the next cases, there are two possible subcases, either we will include the element or not. If the value of the element is greater than the current sum, we will not include the current element and simply return the count without including it.
If the element is less than or equal to current sum, then there are again two sub sub cases, either we will include it or we can exclude it and return the count as the sum of the count of the two possible cases.
CODE:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,sum;
cin>>n>>sum;
int a[2*n];
for(int i=0;i<n;i++)
cin>>a[i];
int totalsum=0;
for(int i=0;i<n;i++)
totalsum=totalsum+a[i];
int actsum=(sum+totalsum)/2;
int dp[n+1][actsum+1];
for(int i=0;i<n+1;i++)
{
for(int j=0;j<actsum+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];
}
}
}
cout<<dp[n][actsum]<<endl;
return 0;
}
INPUT:
6 2
1 2 3 4 5 6
OUTPUT:
5
0 Comments