The question states:
Write a function
canSum(targetSum, numbers)
that takes in atargetSum
and an array of numbers as arguments. The function should return a boolean indicating whether or not it is possible to generate thetargetSum
using numbers from the array. You may use an element of an array as many times as needed. You may assume that all numbers are nonnegative.
In the dynamic programming video I am watching the solution is:
const canSum = (targetSum, numbers) => { if (targetSum === 0) return true; if (targetSum < 0) return false; for (let num of numbers) { const remainder = targetSum - num; if (canSum(remainder, numbers) === true) { return true; } } return false; }
I understand how this code works with many scenarios like canSum(7, [2, 3])
. However I don’t understand this piece: if (targetSum === 0) return true;
that means canSum(0, [2, 3])
will result in true. That’s not how this code should work according to the question. What am I missing here?
Thank you
console.log(canSum(7, [2, 4]))
resulted in false
however
console.log(canSum(0, [2]))
resulted in true
Advertisement
Answer
When it says you can use any numbers as many times as you want, that includes using all of them zero times, and when you do this the sum is 0
. Using this as the base case of the recursion simplifies the algorithm, since you just keep subtracting until you get to 0
.
An alternative way would be to use numbers.includes(targetSum)
as the base case. They’re equivalent because when this is true, one of the iterations of the for
loop will set remainder
to 0
, and the recursive call will have targetSum === 0
.