COUNT OF SUBSETS SUM WITH A GIVEN SUM:
PROBLEM STATEMENT:
You are given an array and a sum and you need to find out how many subsets are there in the array whose sum is equal to the given sum.
QUICK POINTS
1. We will find for each subset if it's sum is equal to the given sum, and will return the count of such subsets.
2. When given sum will be zero, then we will take null subset i.e. subset with no element, the count will be one for sum equal to zero.
3. If there is no element in the array and sum is not equal to zero, then the count will be zero.
STEPS:
1. We are taking user input n, sum, a[n] as size of array, given sum and the array respectively.
2. Now, we are taking a matrix of size (n+1)*(sum+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 given 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[n];
for(int i=0;i<n;i++)
cin>>a[i];
int 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];
}
}
}
cout<<dp[n][sum];
return 0;
}
0 Comments