Algorithm Techniques – Backtracking

Backtracking is a technique for solving problems recursively[1]. It builds the solution by providing candidates, and it removes the candidate when it fails to satisfy the problem constraints.

This usually results in visiting a previous stage of the process, and exploring new possibilities from that step.

Backtracking is used to solve three types of problems:

  1. Decision – searching for one possible solution
  2. Optimization – Searching for the best solution
  3. Enumeration – Searching for all possible solutions

Let’s give an example.

Assuming we are in a maze and we need to find our way out – we start moving in our path.

In case there’s a bifurcation – we need to make a choice where we should go.

With backtracking + recursion, we simply choose to go everywhere.

We set left as our current road, and we move on that road. If we encounter a dead-end, we move back to the bifurcation, we set right as our current road, and we move on to that road. Each decision creates more sub-problems, and in most of them, we backtrack and revert our decision.

In code, this usually requires setting a value, calling the same function again, and in case the function returns fail, we unset the value and continue with the next option.

The pseudo-code for backtracking (general algorithm) is at follows:

[1] Recursion: A function that is calling itself, input parameters will most likely change in each call.

What we’re really doing is that we take each item one by one, check if the constraints are valid if we take such item, and we call the function again with the new information taking in. If at some point, the constraints are invalid, we deselect the item and check for the next one. The function should have a finish condition at start, if we reached the step we wanted, and should return false if it exhausted all the items without any success.

The most important thing in backtracking is the selection of the item and deselection it in case it doesn’t satisfy the problem constraints.

You may also like...