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 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

__________________________________________________ Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________