Below is the program to find the shortest combination to achieve the target sum from a given list of array.

For e.g, Target sum is 5, and list of array is [2, 3, 5]

So possible output is [2, 3] and [5] out of which [5] being the shortest is the answer.

Now here's my query:

1. As per my interpretation shortestCombination gets reset to null on each recursive calls, i.e bestSum(5, numbers), bestSum(3, numbers), bestSum(1, numbers) etc. But how does it magically equate to being [3] and then [3, 2] (instead of null) and finally gets replaced with [5]?

const bestSum = (targetSum, numbers)=>{
    if(targetSum === 0) return [];
  if(targetSum < 0) return null;
  
  let shortestCombination = null;
  for(let num of numbers){
    const remainder = targetSum - num;
    const remainderCombination = bestSum(remainder, numbers);
    if(remainderCombination !== null){
        const combination = [...remainderCombination, num];
      if(shortestCombination === null || combination.length < shortestCombination.length){
       shortestCombination = combination;
      }
    }
    
  }
  return shortestCombination
}

console.log(bestSum(5, [2, 3, 5]))

CodePudding user response：

Let's look at a trivial example: bestSum(4, [4]).

• The first call sets shortestCombination = null, then enters a loop. The loop only iterates the once, and sets remainder = 4-4 = 0. Then it calls bestSum(0, [4]).
  • This second call sees that targetSum == 0 and returns [].
• Back in the first call, remainderCombination = []. It builds combination = [...[], 4] = [4]. Then it checks whether shortestCombination is null or short than combination. It is null, so it sets shortestCombination = [4]. Then the loop ends and the function returns [4].

If that makes sense, then apply it to the next less trivial input: bestSum(2, [1]).

• The first call sets its shortestCombination = null, calls bestSum(1, [1]).
  • The second call sets its shortestCombination = null, calls bestSum(0, [1]).
    • This third call returns [].
  • The second call sets combination = [1], compares this to its shortestCombination (which is null) and sets shortestCombination = [1], returning [1].
• The first call sets combination = [1,1], compares this to shortestCombination (which is null) and sets shortestCombination = [1,1], returning [1,1].

So, yes, each recursive call has its its own shortestCombination; there is no magic.

CodePudding user response：

Elaborating further on the premise Welbong has set:

Let's run the program for bestSum(2, [1, 2])

The loops would run two times for each of 1 and 2. Now let's see what happens when it runs for 1.

bestSum(1, [1, 2]) is called and put on to the stack which again would run for two times, for num, 1 and 2.

Now running for 1, bestSum(0, [1, 2]) will be called which returns an empty array and combination gets set to [...[], 1] or, [1]

Now it again runs for 2, bestSum(-1, [1, 2]) but this times it returns null and hence doesn't change the values of combination and shortestCombination.

So the result of bestSum(1, [1, 2]) turns out to be [1].

This stack is popped out and now we have bestSum(2, [1, 2]) and for num 1, it has returned [1, num] i.e [1, 1]

Now bestSum(2, [1, 2]) runs for 2 it enters the loop, in turn calls bestSum(0, [1, 2]). This again would have run twice for each of the run, however, it returns [] in the beginning itself. So, we have combination as [2] and shortestCombination as [2] again.

So now it's time for the final stack to be popped out bestSum(2, [1, 2]) currently it stores [1, 1] that was the result of iteration through num 1, in the second iteration for 2, we have [2] and this being the shortest replaces [1, 1] and finally [2] is returned.

So as it turns out, each recursive call gives the shortestCombination that is the shortest array resulting from running bestSum(targetSum, nums) for each of the nums. Each results serve to the stack below it and finally the first stack popps out which is the result of shortest of the bestSum(targetSum, nums) running for each of nums.