# subset sum problem-if there is a subset of the given set with sum equal to given sum.

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

a[] = {3, 34, 4, 12, 5, 2}, sum = 9 //given

Output=> True

because There is a subset (4, 5) with sum 9.

we will use dynamic programming here:

c++ implementation:

y is the no. of test cases:

a[] = {3, 34, 4, 12, 5, 2}, sum = 9 //given

Output=> True

because There is a subset (4, 5) with sum 9.

we will use dynamic programming here:

c++ implementation:

y is the no. of test cases:

**
#include <iostream>
using namespace std;
void subset(int a[],int n,int sum)
{
int t[n+1][sum+1];
for(int i=0;i<=n;i++)
t[i][0]=1;
for(int j=1;j<=sum;j++)
t[0][j]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=sum;j++)
{
****if(a[i-1]<=j)
t[i][j]=(t[i-1][j-a[i-1]] || t[i-1][j]);
else
t[i][j]=t[i-1][j];****
}
}
cout<<t[n][sum];
}
int main() {
int y; cin>>y;
while(y--)
{ int n; int sum; int a[n];
cin>>n>>sum;
for(int i=0;i<n;i++)
cin>>a[i];
subset(a,n,sum);
cout<<endl;
}
return 0;
}**