## 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 sum equal to the given sum.

**Examples**

```
Input: values[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
There is a subset (4, 5) with sum 9.
```

```
Input: values[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
There is no subset that add up to 30.
```

## Problem Identification

When you see an algorithmic problem, the first thing you should do is try to identify patterns in the problem statement so that you can relate it to the patterns you have already learned and then try to solve it using that pattern. Algorithmic problems are unlimited but there are only a finite set of patterns and approaches to solve those problems.

All right, So looking at the problem statement, we can notice the following things:

- We’re given a
**number of items** - We have
**choices**- include a value in the subset or don’t. - We have a
**target**sum.

Do these clues ring a bell? Well, it’s a variant of the 0-1 Knapsack problem. Read about the 0-1 Knapsack pattern. In this case, we’re not given the weight of the items, the item values themselves are weights.

## Recursive Solution

All right! So following the same Knapsack problem approach, let’s build a simple choice diagram for our problem so that we can come up with the recursive solution.

**For every given integer (value)**, we have two options

```
[value]
/ \
value > targetSum value <= targetSum
```

`if value > targetSum`

; We can’t include this item in the subset. We don’t have a choice

`if value <= targetSum`

; We have a choice to either include this item in the subset or don’t. Whichever choice leads us to the target sum will be chosen.

Let’s now try to devise a recursive structure for our problem. Let’s say that `SubsetSum(S, n)`

is a boolean that represents whether we can obtain a target sum of `S`

using the values from index `1..n`

or not.

**Recursive structure**

For every item, we have two choices - either include this item in the subset or don’t. We will consider both the choices and determine if we can find a subset of sum S using any of the choices or not.

There will be a subset of sum `S`

using values from index `1..n`

if

we can find a subset of sum

`S`

using values from index`1..n-1`

(**Excluding the nth item**)**or**we can find a subset of sum

`S-values[i]`

using values from index`1..n-1`

(**Including the nth item**)

If the value of the nth item is greater than the target sum `S`

then we can’t include this item in the subset and choice 1 is the only possibility. Let’s write our recursive structure mathematically:

```
SubsetSum(S, n) = SubsetSum(S, n-1); if values[n] > S
SubsetSum(S, n) = SubsetSum(S, n-1) || SubsetSum(S - values[n], n-1); if values[n] <= S
```

**Base condition**

To identify the base condition of recursion, think about the smallest valid input (Empty value array or Zero sum)

```
SubsetSum(S, 0) = false; for S > 0 // We can't obtain a positive sum with no items
SubSetSum(0, n) = true; for any value of n // We can obtain a zero sum by not choosing any items and having an empty subset
```

Allright! Let’s now write the code for our recursive solution

```
import java.util.Scanner;
public class SubsetSumRecursion {
private static boolean hasSubsetSum(int[] values, int targetSum, int n) {
if (targetSum == 0) {
return true;
}
if (n == 0) {
return false;
}
if (values[n - 1] > targetSum) {
return hasSubsetSum(values, targetSum, n - 1);
}
return hasSubsetSum(values, targetSum - values[n - 1], n - 1)
|| hasSubsetSum(values, targetSum, n - 1);
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] values = new int[n];
for (int i = 0; i < n; i++) {
values[i] = keyboard.nextInt();
}
int target = keyboard.nextInt();
keyboard.close();
System.out.println("Has Subset sum: " + hasSubsetSum(values, target, n));
}
}
```

```
$ javac SubsetSumRecursion.java
$ java SubsetSumRecursion
6
3 34 4 12 5 2
9
Has Subset sum: true
```

**Time Complexity:** `O(2^n)`

, Exponential. Learn how to do time complexity analysis for recursive functions

**Space Complexity:** `O(1)`

, no additional space reserved. Only Stack space is used in recursion.

## Method 2: Dynamic Programming Top down solution (Memoization)

We can use dynamic programming to memoize the solutions to subproblmes. Following is the memoized dynamic programming solution.

```
import java.util.Scanner;
public class SubsetSumTopDown {
private static Boolean[][] subsetSumMem;
private static boolean hasSubsetSumRecur(int[] values, int targetSum, int n) {
if (targetSum == 0) {
return true;
}
if (n == 0) {
return false;
}
if (subsetSumMem[targetSum][n] != null) {
return subsetSumMem[targetSum][n];
}
if (values[n - 1] > targetSum) {
subsetSumMem[targetSum][n] = hasSubsetSumRecur(values, targetSum, n - 1);
} else {
subsetSumMem[targetSum][n] = hasSubsetSumRecur(values, targetSum - values[n - 1], n - 1)
|| hasSubsetSumRecur(values, targetSum, n - 1);
}
return subsetSumMem[targetSum][n];
}
private static boolean hasSubsetSumMemoized(int[] values, int targetSum, int n) {
subsetSumMem = new Boolean[targetSum + 1][n + 1];
for (int s = 0; s <= targetSum; s++) {
for (int i = 0; i <= n; i++) {
subsetSumMem[s][i] = null;
}
}
return hasSubsetSumRecur(values, targetSum, n);
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] values = new int[n];
for (int i = 0; i < n; i++) {
values[i] = keyboard.nextInt();
}
int target = keyboard.nextInt();
keyboard.close();
System.out.println("Has Subset sum: " + hasSubsetSumMemoized(values, target, n));
}
}
```

## Method 3: Dynamic Programming Bottom up solution

```
import java.util.Scanner;
public class SubsetSumBottomUp {
private static boolean hasSubsetSum(int[] values, int targetSum) {
int n = values.length;
boolean[][] subsetSum = new boolean[targetSum + 1][n + 1];
subsetSum[0][0] = true;
for (int i = 1; i <= targetSum; i++) {
for (int j = 1; j <= n; j++) {
if (values[j - 1] > i) {
subsetSum[i][j] = subsetSum[i][j - 1];
} else {
subsetSum[i][j] = subsetSum[i - values[j - 1]][j - 1] || subsetSum[i][j - 1];
}
}
}
return subsetSum[targetSum][n];
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] values = new int[n];
for (int i = 0; i < n; i++) {
values[i] = keyboard.nextInt();
}
int target = keyboard.nextInt();
keyboard.close();
System.out.println("Has Subset sum: " + hasSubsetSum(values, target));
}
}
```