Subset Sum is an important and classic problem in computer theory. Given a set o
ID: 3808508 • Letter: S
Question
Subset Sum is an important and classic problem in computer theory. Given a set of integers and a target number, your goal is to find a subset of those numbers that sum to the target number. For example, given the set {3, 7, 1, 8, -3} and the target sum 4, the subset {3, 1} sums to 4. On the other hand, if the target sum were 2, the result is false since there is no subset that sums to 2. The prototype for this method is: public static boolean canMakeSum(int setOfNums [] int targetSum) Assume that the array contains setOfNums. length numbers (i.e., it is completely full). Note that you are not asked to print the subset members, just return true/false. You will likely need a wrapper method to pass additional state through the recursive calls. What additional state would be useful to track?Explanation / Answer
public class subSet
{
public static boolean canMakeSum(int[] setofNums,int targetsum) {
/*base case 1: if the set is only one element, check if element = target*/
if (setofNums.length == 1) {
return (setofNums[0] == targetsum);
}
//base case 2: if the last item equals the target return true
int lastItem = setofNums[setofNums.length - 1];
if (lastItem == targetsum) {
return true;
}
/*make a new set by removing the last item*/
int[] newSet = new int[setofNums.length - 1];
for (int newSetIndex = 0; newSetIndex < newSet.length; newSetIndex++) {
newSet[newSetIndex] = setofNums[newSetIndex];
}
/*recursive case: return true if the subset adds up to the target OR if the subset adds up to (target - removed number)*/
return (canMakeSum(newSet, targetsum) || canMakeSum(newSet, targetsum - lastItem));
}
public static void main(String a[])
{
int set[] = {3,7,1,8,-3};//initialize the Array
int sum =4; //targetsum stored in sum
if(canMakeSum(set,sum)==true)
System.out.println("Found A Subset With Given Sum."); //if subset is found
else
System.out.println("No subset with Given Sum."); //if subset is not found
}
}
/*****OYTPUT WHEN SUM=4******
Found A Subset With Given Sum.
***************************/