I'm working my way through a lesson on dynamic programming, and while working on one of the examples I've run into an interesting bug I haven't been able to figure out. The code is supposed to recursively run through an array of numbers to determine whether the array members can be used to sum to a particular targetNumber. It does that by recursively subtracting the numbers in the array from targetNumber to see if it will decrease to 0.

I pass the parameters to the function canSum like this:

console.log(canSum(8, [2, 3, 5]));

And then here is the function:

const canSum = (targetNumber, numbers) => {

    // if targetnumber is 0, can return true
    if (targetNumber === 0) return true;

    //if targetNumber is less than 0, can return false
    if (targetNumber < 0) return false;

    //loop over array of numbers and evaluate each to see if subtracting it from targetNumber reaches 0
    for (let num of numbers) {
        const remainder = targetNumber - num;

        if (canSum(remainder, numbers) === true) { //if (remainder === 0) {
            return true; 
        }


    }
    return false;
    
}

And the finished code works perfectly, returning true for the above set of inputs.

BUT, as I was writing the code along the way, before I put in the recursive call to canSum, I was trying to test it by just checking if the remainder was equal to 0, and if so, then return true. That's the commented out line of code

if (remainder === 0) {

However, when I use that line instead of the recursive call, the function NEVER returns true. Even when I use console.log to print out the remainder value so I can confirm it is in fact 0, true is never returned and displayed. it always returns false. I'm clearly missing something fundamental here and I just can't figure it out. Thanks for any help you can give me.

CodePudding user response：

Your targetNumber is a const and it's declared within the loop, so it can never be updated. For your if statement to work and also for your recursion to work, you'll want to initialize remainder with targetNumber before the loop, and also subtract from remainder instead of targetNumber within the loop.

Here's and example of those changes:

const canSum = (targetNumber, numbers) => {

    // if targetnumber is 0, can return true
    if (targetNumber === 0) return true;

    //if targetNumber is less than 0, can return false
    if (targetNumber < 0) return false;

    let remainder = targetNumber;

    //loop over array of numbers and evaluate each to see if subtracting it from targetNumber reaches 0
    for (let num of numbers) {
        remainder = remainder - num;
        if (remainder === 0) return true;

        //if (canSum(remainder, numbers) === true) { 
        //    return true; 
        //}
    }
    return false;
}

CodePudding user response：

As you said "whether the array members can be used to sum to a particular targetNumber", so 2 3 5 = 10. They are not equal to 8 so the condition should be false. In your code the "recursion" will pass the remainder on each iteration as:

1. remainder = 6 and recursion function returns 4 after subtracting 2
2. remainder = 4 and recursion function returns 2 after subtracting 2
3. remainder = 2 and recursion function returns 0 after subtracting 2

So you are left with 0 that will return true according to your code logic.
You need to slightly modify the code as:

const canSum = (targetNumber, numbers) => {

    // if targetnumber is 0, can return true
    if (targetNumber === 0) return true;

    //if targetNumber is less than 0, can return false
    if (targetNumber < 0) return false;
    var remainder = targetNumber;

    //loop over array of numbers and evaluate each to see if subtracting it from targetNumber reaches 0
    for (let num of numbers) {
        remainder = remainder - num;

        if (remainder === 0) { //if (canSum(remainder, numbers) === true) { //
            return true; 
        }
    }
    return false;
    
}