Skip to content
Advertisement

Can someone explain canSum to me please

The question states:

Write a function canSum(targetSum, numbers) that takes in a targetSum and an array of numbers as arguments. The function should return a boolean indicating whether or not it is possible to generate the targetSum 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.

User contributions licensed under: CC BY-SA
1 People found this is helpful
Advertisement