# Subset Sum Problem

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

**Problem Description:** Given problem asks you to check whether it is possible to get a subset whose sum is equal to the given sum as in the question if possible you are asked to print "YES" otherwise print "NO".

**Input:** The first line contains an integer 'T' denoting the total number of test cases. Each test case constitutes two lines. The first line contains 'N', representing the number of elements in the set and the second line contains the elements of the set.

**Output:** Print "YES" if there is a subset with a sum equal to the given number and "NO" if there is no subset is present.

**Example:**

Input:
T = 1
N = 7
[5,6,7,8,9,10,11]
sum = 19
Output:
"YES"
{5,6,8}, {11,8}, {10,9} are possible subset with the sum
of elements of the subset equal to given sum as 19.
Input:
T = 1
N = 3
[5,6,7]
sum = 4
Output:
"NO",
no subset is possible since there is no subset
which has sum equal to given sum=4.

(a) Recursion ApproachIn this case, we will consider two possibilities as, we consider the last element and decrease the required sum by that element i.e., required sum=required sum-last element value, array size=array size-1; another case is that we totally neglect the last element's value and decrease the size of the array by one.

required sum=required sum, array size =array size-1;One more case, if the last element's value is greater than the sum then simply decreases the size of the array by one.

The following steps are used:

arr, index position, and requiredsum.sumis zero or not, if thesumis zero then we returntruesince an empty subset is always possible for some element.sumis not zero then we check if the array index is under the correct bound or not it does not then returnfalsesince it is not possible.sumthen also, we cannot include it in our subset-sum.Time Complexity for the above approach is exponential.

Code:Output:(b) Dynamic Programming Approach(i) Top-Down Approach:Here, we will use the memorization method, we will use

dp[n][sum]as our dp state, wherenis the number of elements andsumis the requiredsum, we will initialize all thedp[n][sum]as -1 and whenever we getdp[n][sum]as!=-1we simply return it from the table ofdp[n][sum]without recalculating it again and again.Following steps are used in top-dp:

dp[][]state which will depend on two values as an index and the sum sodp[i][j], whereiis the index value andjis thesumvalue.dp[][]state are filled with -1, and each time we make the recursive call we first check it ondp[][]table if calculated then we simply return it otherwise we calculate it.dp[][]depends same as the recursive approach except that we use memorization technique in top-down which we exclude it in recursive approach.Time Complexity for the above approach is:

O(n*n)Space Complexity for the above approach is:

O(n*n)Code:Output:(ii) Bottom-Up ApproachIn this case, we fill the table in a bottom-up manner, we will use

dp[n][sum]as our dp state wherenis the number of elements in the array andsumis the requiredsum.Following are the base cases:

if sum==0 then dp[i][0]=trueif n==0 and sum !=0 then dp[0][i]=falseFollow steps are used in bottom-up dp for this problem:

dp[n+1][sum+1]state as indexing start from 0.sumis zero and the element are in a valid index range then we makedp[i][0]=truesince an empty subset is always possible.sumjis greater than the array element at indexior not if not then we simply ignore it otherwise we have two possibilities of including and excluding.dp[n+1][sum+1]that isdp[n][sum]value which is formed with the help of n element and requiredsum.Time Complexity for the above approach is:

O(n*n)space complexity for the above approach is:

O(n*n)Code:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: