Overview of backtracking

Simply put, backtracking is an algorithmic technique for solving problems by building a solution incrementally, one piece at a time. It identifies potential solutions by validating every result against a fixed set of constraints. Backtracking is a brute-force approach to finding the desired solution by trying all possible options.

Backtracking suggests that if the current result is unsuitable, backtrack and try other solutions using the same technique. As we will learn later, backtracking very heavily relies on recursion. When exploring the solutions, a bounding function is applied so that the algorithm can check if the solution built so far satisfies the constraints. If it does, it continues searching. If it doesn’t, the branch will be eliminated, and the algorithm will return to the previous level.

Phone unlocking problem

Let us try to understand backtracking through a real example. Imagine that you just got a new phone for yourself and set a 4-digit numeric password for its lock screen before going for a nap. You wake up and forget the password that you set. How will you unlock your phone now?