Backtracking

If you are studying for coding interviews, you have definitely found problems that ask you to find all possible solutions or to try all possible configurations which might be a bit of a challenge. Those kinds of problems can be tackled by using a backtracking algorithm.

What is backtracking?

Backtracking is a general algorithm used to solve computational problems where all possible scenarios are observed in order to find a solution or solutions.

Let's explore the following problem, given an array of positive integers and a target integer greater than cero, find all possible configurations/combinations of numbers that added will be equal to the target.

Let’s do an example of the journey our code would have to do if the given array were [2,3,4] and our target 6. It should iterate recursively through each element in the array and keep on adding them until they are equal to or greater than the target. If it is equal, we found one of the configurations that satisfy the condition, so we save it and go back to the previous step. if it is greater than the target, we proceed to discard the current configuration and return to the previous step. Let’s see the code and analyzed it further.

The magic of backtracking happens in the helper function, therefore I will focus my attention on it. Line 8 to 11 execute when the current combination sum is equal to the target, it adds the current combination to results and returns in order to go back to the previous step. Line 12 to 14 execute when the current combination sum is greater than the target, forcing the algorithm to return to the previous step. Line 15 to 21 we iterate over each element of the array and try all of the possible configurations with each one of them. Each time the current combination sum reaches or surpasses the target it returns the previous call and removes the last element, subtracts it from the current sum, and tries the possible configurations with the next element in the array. Let’s see how the journey of the first element in the array, remember our array is [2,3,4], and our target is 6.

A similar journey is going to happen to all elements on the array until all combinations are tried. All combinations that satisfy our condition would be saved in the result variable.