Given a target sum and an array of positive integers, return true if any combination of numbers in the array can add up to the target value. Each number in the array may only be used once. Return false if the numbers cannot be combined to sum to the target value.
subsetSum(2, [1, 10, 5, 3]); // false
subsetSum(10, [1, 10, 5, 3]); // true
subsetSum(9, [1, 10, 5, 3]); // true
subsetSum(19, [1, 10, 5, 3]); // true
subsetSum(17, [1, 10, 5, 3]); // falseOne thing to notice right away about this problem is it is more complicated than a nested for loop. We need to check every combination of numbers in the array until we find one whose components sum to the target, or until we've exhausted combinations. This includes checking if any value in the array is equal to the target, if any value added to any other value sums to the target, if any combination of three numbers in the array sums to the target, etc.
You might sense that doing this naively will involve repeating a lot of work. For example, if I wanted to check whether 1 + 10 equals the target, and then I want to check whether 1 + 10 + 5 equals the target, I may find myself repeating the 1 + 10 calculation. That's expensive (and complicated), so it's something we want to avoid. One alternative is to find a way to keep track of each sum as we calculate it, and then somehow access and use those sums we are keeping track of as we go along generating more sums.
A simple way to keep track of a collection of numbers is to use an array to store them in some useful order, so let's start by initializing an array (we'll call it sumsArray) to keep track of our sums. We know that if we work our way through every possible combination of numbers in the original array, we are going to add each of the numbers in the original array into the sumsArray, along with the sums of each of the numbers added to each other number, along with the sums of each of the numbers added to those sums, etc.
This suggests a pattern where for each number in the original array, we add it to the sumsArray and then add it to every other sum already in the sumsArray. If we loop through the original array and do this, we will end up with every combination stored in the sumsArray. (Of course, we can stop at any point if one of the sums in the sumsArray matches our target!)
To outline an example in words:
/*
example: subsetSum(17, [1, 10, 5, 3])
=> set of possible sums: [0]
=> add 1 to each possible sum
=> set of possible sums: [0, 1]
=> add 10 to each possible sum
=> set of possible sums: [0, 1, 10, 11]
=> add 5 to each possible sum
=> set of possible sums: [0, 1, 10, 11, 5, 6, 15, 16]
...etc
*/
Written in code, it will look something like this:
function subsetSum(target, arr) {
let sumsArray = [0] // I initialized the sums array with a 0 inside because (a) if arr is empty, I still
// have a sum to compare to the target, and (b) this way I can perform the same action repeatedly: adding
// the current element of the original array to all preexisting sums, then pushing the result of that
// addition into the sumsArray as well. I don't have to worry about an extra step for pushing the element
// itself into the sumsArray, because the element plus 0 will always just be the element.
for (let i = 0; i < arr.length; i++) {
let sumsArrayCopy = [...sumsArray] // I am making a copy because we are now going to iterate through the
// sumsArray *and* add elements to it, and I don't want to break the call stack!
for (let j = 0; j < sumsArrayCopy.length; j++) {
let newSum = arr[i] + sumsArrayCopy[j] // Here I am adding the current element in the original array
// (outer for loop) to the current element in the sumsArrayCopy (inner for loop), to create a new sum
// to add to the collection.
if (newSum === target) { // If we've created a sum that matches our target, we're done!
return true
}
else if (newSum < target) { // Here I do this extra check because there is no point in adding a sum to
// the sumsArray if it's already larger than the target. No matter what else we add to it in the future,
// we'll never hit our target.
sumsArray.push(newSum)
}
}
}
return false // If I hit this line without returning true, then I've checked every possible sum of numbers
// from the original array without finding my target.
}You can implement the same approach as above using a Set (an ES6 data structure), instead of an array, to keep track of the sums. Here is a link for learning more about sets: https://exploringjs.com/es6/ch_maps-sets.html#sec_set. Below is how the function would look using a Set.
function subsetSum(target, arr) {
const possibleSums = new Set([0]);
for (const element of arr) {
const currentPossibleSums = new Set(possibleSums);
for (const sum of currentPossibleSums) {
const newSum = sum + element;
if (newSum === target) return true;
if (newSum < target) possibleSums.add(newSum);
}
}
return false;
}In our functions above, we used an iterative solution, but, as we've been told repeatedly, a problem that can be solved iteratively can also be solved recursively (and vice versa). One recursive approach to this problem would involve subtracting various combinations of numbers in the original array from the target value and seeing if we can get the target down to 0. (If subtracting a certain collection of numbers from the target gets us to 0, we know that that collection of numbers adds up to the target, which is our goal.)
This means that if the target falls below 0, we've gone too far – we've come up with a combination of numbers whose sum is greater than the target. If the target remains above 0, we haven't gone far enough, so we can keep subtracting numbers from the target.
So we know the condition under which our function should return true: if the target has been reduced to 0. And we know that our function should return false if our target goes below 0 – or if we've exhausted number combinations to try. So those can be treated as the base cases of our recursive function. But what happens in the recursive case? Well, we definitely want to call the function again with target being decreased by the value of one of the numbers in the original array. But what if there exists a collection of numbers in the array that sum up to the target, but the number we select isn't among them?
One way to deal with this is to think of the recursive call stack as a decision tree. As we consider each number in the original array, we know that it may be a member of a collection of numbers that sums to the target, or it may not. So we actually have to consider both cases. In other words, we need to make recursive calls for both options. And then, as we consider the next number, we know that it may be a member of a collection of numbers that sums to the target, or it may not. So we've reached another branching point. If we consider each element of the original array in turn, and create subtrees for their inclusion and exclusion in that special collection, we will end up considering every possible combination of numbers in the original array.
Here is an implementation in code:
function subsetSum(target, arr, idx = 0) { // We are initializing the index (idx) to 0 here and
// incrementing it as we make successive recursive calls. It's another way of looping through the
// original array (arr) of numbers.
if (target === 0) return true; // This is one of our base cases. If we get the target down to exactly 0,
// we've found a combination of numbers that sum to it.
if (target < 0 || idx === arr.length) return false; // If target goes below 0, we know the current
// combination we're testing isn't right. (Don't worry – this condition can be met many times in the
// recursive calls without it being met in the original function call.)
const num = arr[idx];
const whenExcluded = subsetSum(target, arr, idx + 1); // This is the branch where the current number is
// not part of the combinations we are testing.
const whenIncluded = subsetSum(target - num, arr, idx + 1); // This is the branch where the current number
// *is* part of the combinations we are testing.
return whenExcluded || whenIncluded; // This line will only execute in the original function call when the
// recursive calls have all been completed. If there exists a combination that includes the number at index
// 0 or excludes it and that sums to the target, this will return true for the original function call.
}This implementation works, but it isn't very efficient. It creates a binary tree of recursive calls, which has a time complexity of O(2^n), where n is the length of the original array. It runs into the problem we identified earlier of repeating subcalcuations. Put another way, many of the nodes on the tree (recursive calls) are the same. In a situation where you find yourself repeating calculations, the word that should pop into your head is "memoization." Memoization is what it sounds like – you write down the values you've calculated somewhere, so that when you need to calculate them again, you just look them up instead.
In this problem, we can use an object to store the booleans for each value of target, like so:
function subsetSum(target, arr, idx = 0, memo = {}) { // Here we add a "memo" object to the parameters.
if (memo.hasOwnProperty(target)) return memo[target]; // Here we can just return the stored value
// (a boolean) for a particular value of target, if we've already calculated it.
if (target === 0) return true;
if (target < 0 || idx === arr.length) return false;
const num = arr[idx];
const whenExcluded = subsetSum(target, arr, idx + 1, memo);
const whenIncluded = subsetSum(target - num, arr, idx + 1, memo);
const result = whenExcluded || whenIncluded;
memo[target] = result; // This is where we add boolean values to the memo object, corresponding to the
// target we are currently at.
return result;
}This is a complicated problem, so you may want to dig into a bit more. Here is a visual illustrating how memoization saves us time in the second approach, and below that are some useful links.
