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.