DETERMINE IF THERE IS A SUBSET IN A GIVEN ARRAY WHOSE SUM IS EQUAL TO THE GIVEN SUM-( SUBSET SUM PROBLEM)

 You are given an array and a sum. We have to determine if there is a subset whose sum of the elements is equal to the given sum.

CODE:

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int t; //no of test cases

    cin>>t;

    while(t--)

    {

        int n,sum; // size of array and given sum

        cin>>n>>sum;

        int a[n];

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

            cin>>a[i]; //array elements

        bool dp[n+1][sum+1];  //boolean table to store true or false for each element

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

        {

           for(int j=0;j<sum+1;j++)

           {

               if(j==0)

                dp[i][j]=true; //initialization

               else if(i==0)

                dp[i][j]=false;  //initialization

               else if(a[i-1]<=j)

                dp[i][j]=(dp[i-1][j-a[i-1]])|| dp[i-1][j];  //choosing if we will take current element 

               else if(a[i-1]>j)

                dp[i][j]=dp[i-1][j]; //if the current element is greater than sum then, we will not take

           }

        }

        if(dp[n][sum]==1)

            cout<<"YES"<<endl;

        else

            cout<<"NO"<<endl;

    }

    return 0;

}

INPUT:

3

4  5

1  2  3  5

10  4

100  2  3  4  5  1  6  1  9  150

5  100

10  200  150  50  10

OUTPUT:

YES

YES

NO

Also check:

EQUAL SUM PARTITION