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:
Time Complexity: O(2n).
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 ith 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 Cases SubsetSum(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:
Output: From DP: true
