Some simple tips for Combination Sum -Backtracking

We are asked to find all the combinations that sum a target, from a list of integers. And in this case, the combinations can contain duplicates from the original list.

This type of problem is a common interview algorithm, but it might take some 'digestion' over time to get familiar with. Even though the code is short and relatively simple, the concepts behind it like depth-first search, stacks, recursion, and backtracking, are a lot of information to take in. So I will simplify some of the steps in the algorithm but by no means can explain all of these concepts in a short article.

Backtracking

The main steps to do a backtracking algorithm involve: making a recursive callback function which in this case is called combinations.

Then adding a base case to exit the recursion:

if(target === 0 )

And lastly doing a depth-first search:

for(let i = start; i < candidates.length; i++)

Then a temporary list stack considers each option:

stack.push(candidates[i])

Next, the current number being considered is subtracted from the target and passed into the recursion.

target - candidates[i]

And last we move on from that option:

stack.pop()

Needless to say, recursion callbacks are very complex to visualize step by step, but all these operations are 'stacked' on a 'waiting list' as the code runs line by line and then ran one by one as they are popped out of the runtime waiting list.

let combinationSum = (candidates, target) => {

    let result  = []
    candidates.sort((a,b) => a - b)

    combinations(candidates, target, [], result, 0)

    return result
};

let combinations = (candidates, target, stack, result, start) => {

    if(target < 0 ){
        return
    }else if(target === 0 ){
        console.log(stack)
        console.log(target)
        result.push([...stack])
        console.log(result)
    }else{
        for(let i = start; i < candidates.length; i++){
            stack.push(candidates[i])
            combinations(candidates, target - candidates[i], stack, result, i)
            stack.pop()
        }
    }
}

Scope

This is an interesting factor about these backtracking problems because we define the result array outside our combinations callback and it is modified inside the recursion scope and then returned as the answer back in the outer combinationSum scope.

However, the array that contains the inner list of combinations which I call stack in this case, has to be defined in the scope of the combinations recursive function and not in the outer combinationSum scope for it to properly store the values of the different recursions.

Feel more than welcome to reach out with any ideas/comments at Linkedin or Twitter, or check out my portfolio.