Q:

# Subset Sum

Given an array of size n and a sum K, determine whether any subset is possible with that sum or not. Print "yes" if there is any subset present else print "no".

```    Input & output:
In the first line the input will be n and K, space separated.
The next line contains the array elements

Output will be "yes" or "no"
```

Example with explanation:

Example 1:

```    Input:

The array size be: 5
The sum be: 11
The Elements be: 5 6 7 3 9

Output:
Yes

Explanation:
5 & 6 sums to 11. Thus the subset can be [5, 6] and output will be "yes".
```

Example 2:

```    Input:

The array size be: 5
The sum be: 11
The Elements be: 5 6 7 3 9

Output:
Yes

Explanation:
5 & 6 sums to 11. Thus the subset can be [5, 6] and output will be "yes".```

Of course the naïve solution would be to generate all possible subsets and check their sum equals to K or not. But it would of course be computationally exponential to generate all possible subsets.

To do so, the recursion would be:

For nth element the cases are:

1. Consider the nth element as part of solution subset and recur for n-1 elements for obtaining sum (K-arr[n]).
2. Don't consider nth element as part of solution subset and recur for n-1 elements for obtaining sum (K).

So, the recursion function can be written as:

```    f(n,K)=f(n-1,K) | f(n-1,K-arr[n-1])
```

Where,

```    f(n,K)= value for problem with array size n and sum K which can be either true or false
```

Now base case would be,

f(0,0) = true f(0,i) = false for 1 ≤ i ≤K f(i,0) = true 1 ≤ i ≤ n

Here comes the concept of sub problem. Initially the problem is for size n and sum K. Then it gets reduced to {size (n-1) and sum K} or {size (n-1) and (sum K-arr[n-1])}

So if you draw the recursion tree there will be many such sub-problem which will be overlapping ones. That means we will re-compute same sub-problems again and again. That’s why we need to store the value of sub-problems and use dynamic programming.

Converting to dynamic programming:

```    1)  Initialize  dp[n+1][sum+1] which is a Boolean table to false
2)  Convert the base cases for recursion
for i=1 to sum
dp[0][i]=false;
for i=0 to n
dp[i][0]=true;
3)  Build the table as per the recursion formula.
for i=1 to sum
for j=1 to n
//if sub-sum i>jth element then only we can take that
if(i>=arr[j-1])
//consider both case mentioned in solution approach
dp[j][i]=dp[j-1][i] | dp[j-1][i-arr[j-1]];
else                       // don't take jth element
dp[j][i]=dp[j-1][i];

if(i==sum)
if(dp[j][i]){
return true;
End If
end for
end for

4)  If not returned from the loop
return false;
```

C++ Implementation:

``````#include <bits/stdc++.h>
using namespace std;

bool subsetSum(vector<int> arr, int n, int sum)
{
//DP matrix
bool dp[n + 1][sum + 1];

memset(dp, false, sizeof(dp));

//base case
for (int i = 1; i <= sum; i++)
dp[0][i] = false;

for (int i = 0; i <= n; i++)
dp[i][0] = true;

//build the table
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
if (i >= arr[j - 1])
dp[j][i] = dp[j - 1][i] | dp[j - 1][i - arr[j - 1]];
else
dp[j][i] = dp[j - 1][i];

if (i == sum) {
if (dp[j][i]) {

return true;
}
}
}
}
return false;
}

int main()
{
int t, n, k, item;

cout << "Enter array length,n\n";
cin >> n;

cout << "Enter sum,K\n";
cin >> k;

cout << "Enter elements\n";
vector<int> a;
for (int j = 0; j < n; j++) {
scanf("%d", &item);
a.push_back(item);
}

if (subsetSum(a, n, k))
cout << "yes\n";
else
cout << "no\n";

return 0;
}``````

Output

```RUN 1:
Enter array length,n
5
Enter sum,K
11
Enter elements
5 6 7 3 9
yes

RUN 2:
Enter array length,n
5
Enter sum,K
22
Enter elements
5 6 7 3 9
yes```