Backtracking Algorithm

Backtracking is a general algorithm that can be used to find one or multiple solutions to some computational problems. Basically, how we use backtracking we make some sort of choice if that choice is wrong we ‘backtrack’ to where we can make a different choice and move forward from there until we get a correct solution or run out of options in a case where there is no solution.

Photo by Daniel Irwin on Unsplash

From this, we can see how backtracking is very often associated with recursion where we recursively call a function to move through the different options until we break out of the recursion with criteria for a valid solution or if we don't find a solution. A good visual example of backtracking is a maze problem where you can choose different paths if the path you choose leads to a dead-end and not the final goal, you backtrack back to where there was a different path to choose and move forward from there repeating this until you reach your goal. For problems like this, we would also keep track of where you visited in the maze to prevent an infinite back and forth loop. Backtracking has many uses and can often be used as an algorithm to solve puzzle problems as I mentioned before with the maze, also sudoku, or the n-queen problem (which is a puzzle where you place queens on a chessboard in a way where they can’t attack each other).

The backtracking algorithm isn’t limited to puzzle-type problems either. There are several problems where we can use the backtracking algorithm. To show this I will code out the solution in JavaScript to the ‘Combination Sum’ problem from leetcode using backtracking. The problem takes in an array of numbers and a target number, our goal is to return an array of arrays where the numbers add up to the target (we can repeat numbers). We first need to create two arrays our result array and a temporary array we will add to and remove from (backtrack on) until we get a correct solution to be added to our results array. Then we create our recursive function which takes the argument of an index and a target number. From there were add conditional statements, to break out of our recursive function if our target is below 0 our total in our temporary array is too high (and not a solution) so we backtrack and remove the last item from our temporary array and add the next value from our original array. If our index is equal to the original array length we break out as there are no more numbers to check. If our target is equal to zero we have found a valid solution in the temporary array as we are adding the current number to the temporary array and taking it away from the target on each recursion. We begin by calling our recursive function at index 0 with the original target. Below is the coded out solution which is easier to follow if you see how the recursion is working:

To illustrate the backtracking working through this function here is a list of what is put in the temp array and out of it for the input array and target being [2, 3, 6, 7] and 7 respectively.

[ 2 ]
[ 2, 2 ]
[ 2, 2, 2 ]
[ 2, 2, 2, 2 ]      //We backtrack here to remove the last 2
[ 2, 2, 2, 3 ]      //We backtrack here to remove the 3
[ 2, 2, 2, 6 ]      //We backtrack here to remove the 6
[ 2, 2, 2, 7 ]      //We backtrack here to remove the 7 & 2
[ 2, 2, 3 ] //We push this as a solution & backtrack to remove the 3
[ 2, 2, 6 ]         //We backtrack here to remove the 6
[ 2, 2, 7 ]         //We backtrack here to remove the 7 & 2
[ 2, 3 ]     //The same pattern continues the until we reach the end
[ 2, 3, 3 ]
[ 2, 3, 6 ]
[ 2, 3, 7 ]
[ 2, 6 ]
[ 2, 7 ]
[ 3 ]
[ 3, 3 ]
[ 3, 3, 3 ]
[ 3, 3, 6 ]
[ 3, 3, 7 ]
[ 3, 6 ]
[ 3, 7 ]
[ 6 ]
[ 6, 6 ]
[ 6, 7 ]
[ 7 ]               //This is also as solution

So this is backtracking with recursion it is useful to work through a problem and write it out to see where the backtracking is taking place.

This youtube video walks through the leetcode problem I used above, explains and codes out a backtracking solution in Java https://www.youtube.com/watch?v=yFfv03AE_vA