# Subset sum problem  Difficulty Level Easy
Array Dynamic Programming

In the subset sum problem, we are given a list of all positive numbers and a Sum. We need to check if there is a subset whose sum is equal to the given sum.

## Example  Input

List of numbers: 1 2 3 10 5

sum: 9

Output

true

Explanation

for a subset {1,3,5} sum of all values (1+3+5) = 9 ,which is equal to the given sum. So our answer is yes.

## Approach for Subset sum problem  • For each element in the given list, we have two options.
1. To include the element in the subset
2. To exclude the element from the subset.
•  If we include the element in the subset then the value of sum decreases by the value of the element.
• If we excluded the element the value of sum remains the same.
• After repeating these steps for each element if the value of sum decreases to zero then definitely we have a subset whose sum is equal to the given sum and we return true.
• Otherwise, we return false. ## Recursive solution  ### C++ code

```#include <stdio.h>
bool check(int a[], int n, int sum)
{
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;
if (a[n-1] > sum)
return check(a, n-1, sum);
return check(a, n-1, sum) ||
check(a, n-1, sum-a[n-1]);
}
int main()
{
int a[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = sizeof(a)/sizeof(a);
if (check(a, n, sum) == true)
printf("Found");
else
return 0;
}```
`Found`

### Java code

```class subset {

static boolean check(int a[],
int n, int sum)
{
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;
if (a[n-1] > sum)
return check(a, n-1, sum);
return check(a, n-1, sum) ||
check(a, n-1, sum-a[n-1]);
}
public static void main (String args[])
{
int a[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = a.length;
if (check(a, n, sum) == true)
System.out.println("Found");
else
}
}```
`Found`

### Complexity analysis for Subset sum problem

#### Time complexity

The recursive approach will check all possible subset of the given list. So, the time complexity will be exponential.

The Stock Span Problem

## Dynamic programming approach for Subset sum problem  The recursive approach will check all possible subset of the given list. The subproblem calls small calculated subproblems many times. So to avoid recalculation of the same subproblem we will use dynamic programming. We will memorize the output of a subproblem once it is calculated and will use it directly when we need to calculate it again. The time complexity of the dynamic programming approach is O(n*sum).

### C++ code

```bool check(int a[], int n, int sum)
{
bool subset[n+1][sum+1];
for (int i = 0; i <= n; i++)
subset[i] = true;
for (int i = 1; i <= sum; i++)
subset[i] = false;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= sum; j++)
{
if(j<a[i-1])
subset[i][j] = subset[i-1][j];
if (j >= a[i-1])
subset[i][j] = subset[i-1][j] ||
subset[i - 1][j-a[i-1]];
}
}

return subset[n][sum];
}

int main()
{
int a[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = sizeof(a)/sizeof(a);
if (check(a, n, sum) == true)
printf("Found");
else
return 0;
}```
`Found`

### Java code

```class checksubset {
static boolean check(int a[],
int n, int sum)
{
boolean subset[][] =
new boolean[sum+1][n+1];
for (int i = 0; i <= n; i++)
subset[i] = true;
for (int i = 1; i <= sum; i++)
subset[i] = false;
for (int i = 1; i <= sum; i++)
{
for (int j = 1; j <= n; j++)
{
subset[i][j] = subset[i][j-1];
if (i >= a[j-1])
subset[i][j] = subset[i][j] ||
subset[i - a[j-1]][j-1];
}
}

return subset[sum][n];
}
public static void main (String args[])
{
int a[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = a.length;
if (check(a, n, sum) == true)
System.out.println("Found");
else
}
}```
`Found`

### Complexity analysis for Subset sum problem

#### Time complexity

O(sum*n) here the sum is given sum and n is the number of elements in the array. We are traversing the 2D matrix to solve the problem and the answer is obtained at the bottom right corner of the matrix.