SubsetSumProblem.java

/*
https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
https://www.techiedelight.com/subset-sum-problem/


To Do - Print Subsets and Solve in O(sum)
Further - Does this work on negative numbers?


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 given sum.
Example:
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True //There is a subset (4, 5) with sum 9.

A Naive Approach would be to form all subsets and see if their sum equals the given sum. 
Number of subsets = 2^n
Time rqd to check if the sum of subset equals the given sum = n (at most, becuase maximum size of subset can be n)
Time Complexity - O(n 2^n)


RECURSION
We have two choices - 
1. Include the current item and recur with remaining sum
2. Exclude current item and recur
*/

publicbooleanisSubset(intA[], intcurrent, intsum){
//Base Case 1: sum == 0
if( sum == 0 ) returntrue;

//Base Case 2: we have exhausted all elements and sum is still not 0
elseif( n==0 && sum!=0 ) returnfalse;

//Does the current element's value exceed the remaining sum? ==> Current element has to be EXCLUDED
if( A[current-1] > sum ) returnisSubset(A, current-1, sum);

//Explore both choices - Include and Exclude
return (isSubset(A, current-1, sum) || isSubset(A, current-1, sum-A[current-1]));
}

/*
Time Complexity - O(2^n)
We explore two choices at each recursion.

The above solution may try all subsets of given set in worst case. Therefore time complexity of the above solution is exponential. The problem is in-fact NP-Complete (There is no known polynomial time solution for this problem).
*/

//DYNAMIC PROGRAMMING - PSUEDOPOLYNOMIAL - BOTTOM-UP APPROACH

publicbooleanisSubset(intA[], intn, intsum){
booleanT[][] = newboolean[n+1][sum+1];

//if sum = 0, then answer is true
for(inti=0;i<=n;i++) T[i][0] = true;

//if the set is input is an empty set
for(intj=0;j<=sum;j++) T[0][j] = false;

for(inti=1;i<=n;i++){
for(intj=1;j<=sum;j++){

//Does the current element's value exceed the remaining sum? ==> Current element has to be EXCLUDED
if(A[i-1] > j) T[i][j] = T[i-1][j];

//Explore both - Include and Exclude
elseT[i][j] = (T[i-1][j] || T[i-1][j-A[i-1]]);
 }
 }

returnT[n][sum];
}

/*
Time Complexity - O(n*sum)
*/

//RECURSION USING MEMOIZATION - TOP-DOWN APPROACH

publicbooleanisSubset(intA[], intcurrent, intsum, HashMap<String, Boolean> map){
if(sum==0) returntrue;

elseif(n==0 && sum!=0) returnfalse;

Stringkey = current+"|"+sum;
booleaninclude = false;
booleanexclude = false;
if(!map.containsKey(key)){
if( A[current-1] > sum ) include = isSubset(A, current-1, sum-A[current-1], map);
exlude = isSubset(A, current-1, sum, map);
map.put(key, (include || exclude));
 }
returnmap.get(key);
}

/*
Time and Space Complexity - O(n*sum)
*/