SubSet Sum Problem Using Dynamic Programming

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.

Solution:

#include<iostream>

#include<stdio.h>

using namespace std;

bool isSubsetSum(int set[], int n, int sum)

{

   

    bool subset[sum+1][n+1];

 

    // If sum is 0, then answer is true

    for (int i = 0; i <= n; i++)

      subset[0][i] = true;

 

    // If sum is not 0 and set is empty, then answer is false

    for (int i = 1; i <= sum; i++)

      subset[i][0] = false;

 

     

     for (int i = 1; i <= sum; i++)

     {

       for (int j = 1; j <= n; j++)

       {

         subset[i][j] = subset[i][j-1];

         if (i >= set[j-1])

           subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];

       }

     }

 

    

 

     return subset[sum][n];

}

 

int main()

{

    int T = 0 ;

    cin>>T;

    int *a;

    int n = 0;

    int sum = 0 ;

    for(int t = 0 ; t < T ; t++)

    {

            cin>>n;

            a = new int[n];

            for(int i = 0 ; i < n ; i++)

            {

                    cin>>a[i];

            }

            

            cin>>sum;

  if (isSubsetSum(a , n , sum ) == true)

     cout<<"YES"<<endl;

  else

     cout<<"NO"<<endl;

     delete []a;

  }

  return 0;

}