Write a function ‘subsetSum’ that is given an array of integers and a target number. It should return true if there is a subset of the array that sums up to the target and returns false otherwise. A subset can be any size and the elements do not have to appear consecutively in the array.
Examples:
subsetSum([3, 7, 4, 2], 5) -> true (3 + 2 = 5)
subsetSum([3, 34, 4, 12, 5, 12], 32) -> true (3 + 12 + 5 + 12 = 32)
subsetSum([8, 2, 4, 12], 13) -> false
subsetSum([8, -2, 1, -3], 6) -> true (8 + 1 + (-3) = 6)
Recursive vs Backtracking
We can solve this with recursion or backtracking. The recursion is the easier case and since this problem is in the easy section, we’ll go with recursion.
Keep in mind that these recursive calls are expensive in that it adds more a lot of function calls to the stack.
Recursive Solution
function subsetSumR(arr,target,index=0) {
//base case
if (target===0) {
return (arr[index]===target);
}
if (index>=arr.length-1) {
return (arr[index]===target);
}
//recursive case
return (subsetSumR(arr,target-arr[index],index+1) || subsetSumR(arr,target,index+1));
}
Discussion
Base Case:
If we’re at the end of the array, check if our last remaining element is equal to the target. If the number isn’t needed, the target number would be zero and we return true as well.
Recursive Case:
Check two scenarios:
-use current number, and check the rest. Target number would be prior target minus current number since we use the current number.
-don’t use current number, and check the rest. Target number would be prior target since we don’t use the current number.
If either returns true, then return true. Otherwise, return false.