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:

#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;
}