## DEV Community is a community of 847,300 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# 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.