# Subset Sum

Subset Sum: Here, we are going to learn how to solve the subset sum problem which has been featured in many interview rounds like Amazon, Microsoft?
Submitted by Radib Kar, on February 29, 2020

Description:

In this article, we are going to see how to solve the subset sum problem which has been featured in many interview rounds like Amazon, Microsoft?

Problem statement:

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".
```

Solution Approach:

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[i]=false;
for i=0 to n
dp[i]=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[i] = false;

for (int i = 0; i <= n; i++)
dp[i] = 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
```