This post is completed by 1 user

Add to List 
162. Dynamic Programming  Subset Sum Problem
Objective: Given a set of positive integers, and a value sum S, find out if there exists a subset in an array whose sum is equal to the 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:
Every element in the array has two options, either we will include that element in the 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 the subset we will put 1 in that particular index else put 0.
 So we need to make every possible subset and check if any of the subsets 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 a better explanation.
Approach: Dynamic Programming (BottomUp)
Base Cases:
 If no elements in the set then we can't make any subset except for 0.
 If the 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 = SarrA[i], n=n1
 If exclude it => S, n=n1.
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 Cases SubsetSum(arrA, n, S) = SubsetSum(arrA, n1, S) SubsetSum(arrA, n1, SarrA[n1])
How to track the elements.
 Start from the bottomright corner, backtrack, and check from the True is returning.
 If the value in the cell above is false, the current cell has become true after including the current element. So include the current element and check for the sum = sum  current element.
Output:
Output: From DP: true