**Objective: **Given a set of positive integers, and a value *sum S*, find out if there exist a subset in array whose sum is equal to given *sum S.*

Example:

int[] A = { 3, 2, 7, 1}, S = 6 Output: True, subset is (3, 2, 1}

We will first discuss the recursive approach and then we will improve it using Dynamic Programming.

**Recursive Approach:**

For every element in the array has two options, either we will include that element in subset or we don’t include it.

- So if we take example as int[] A = { 3, 2, 7, 1}, S = 6
- If we consider another int array with the same size as A.
- If we include the element in subset we will put 1 in that particular index else put 0.
- So we need to make every possible subsets and check if any of the subset makes the sum as S.
*If we think carefully this problem is quite similar to “**Generate All Strings of n bits“**See the code for better explanation.*

**Complete Code:**

public class SubSetSumRecursion { | |

public static void find(int[] A, int currSum, int index, int sum, | |

int[] solution) { | |

if (currSum == sum) { | |

System.out.println("\nSum found"); | |

for (int i = 0; i < solution.length; i++) { | |

if (solution[i] == 1) { | |

System.out.print(" " + A[i]); | |

} | |

} | |

} else if (index == A.length) { | |

return; | |

} else { | |

solution[index] = 1;// select the element | |

currSum += A[index]; | |

find(A, currSum, index + 1, sum, solution); | |

currSum -= A[index]; | |

solution[index] = 0;// do not select the element | |

find(A, currSum, index + 1, sum, solution); | |

} | |

return; | |

} | |

public static void main(String[] args) { | |

int[] A = { 3, 2, 7, 1}; | |

int[] solution = new int[A.length]; | |

find(A, 0, 0, 6, solution); | |

} | |

} |

**Time Complexity: O(2 ^{n}).**

**Approach: Dynamic Programming (Bottom-Up)**

**Base Cases:**

- If no elements in the set then we can’t make any subset except for 0.
- If sum needed is 0 then by returning the empty subset we can make the subset with sum 0.

**Given** – Set = **arrA[]**, Size = **n**, sum = **S**

- Now for every element in he set we have 2 options, either we include it or exclude it.
- for any i
^{th}element- - If include it => S = S-arrA[i], n=n-1
- If exclude it => S, n=n-1.

Recursive Equation:Base Cases:SubsetSum(arrA, n, S)= false, if sum > 0 and n == 0 SubsetSum(arrA, n, S)= true, if sum == 0 (return empty set)Rest CasesSubsetSum(arrA, n, S) = SubsetSum(arrA, n-1, S)|| SubsetSum(arrA, n-1, S-arrA[n-1])

**How to track the elements.**

- Start from the bottom-right corner and backtrack and check from the True is coming.
- If value in the cell above if false that means current cell has become true after including the current element. So include the current element and check for the sum = sum – current element.

**Complete Code:**

public class SubSetSum { | |

public static boolean subSetDP(int[] A, int sum) { | |

boolean[][] solution = new boolean[A.length + 1][sum + 1]; | |

// if sum is not zero and subset is 0, we can't make it | |

for(int i=1;i<=sum;i++){ | |

solution[0][i]=false; | |

} | |

// if sum is 0 the we can make the empty subset to make sum 0 | |

for(int i=0;i<=A.length;i++){ | |

solution[i][0]=true; | |

} | |

// | |

for(int i=1;i<=A.length;i++){ | |

for(int j=1;j<=sum;j++){ | |

//first copy the data from the top | |

solution[i][j] = solution[i–1][j]; | |

//If solution[i][j]==false check if can be made | |

if(solution[i][j]==false && j>=A[i–1]) | |

solution[i][j] = solution[i][j] || solution[i–1][j–A[i–1]]; | |

} | |

} | |

return solution[A.length][sum]; | |

} | |

public static void main(String[] args) { | |

int[] A = { 3, 2, 7, 1}; | |

System.out.println("\nFrom DP: " + subSetDP(A, 6) ); | |

} | |

} |

Output: From DP: true