Identifying the backtracking search pattern
Backtracking is a powerful technique that emulates brute-force solutions to solve a wide range of problems. Most problems that can be solved using the backtracking search technique are medium or hard problems for which no other optimised solutions exist. We define an initial problem state and make a set of choices to explore the entire problem space and search for a solution. We terminate the search and return the solution state along with the path from the initial problem state as soon as a solution is found.
If the problem statement or its solution follows the generic template below, it can be solved using backtracking search.
Template:
Given an initial problem state, find any solution state that can be reached from it by making a set of choices at each step. Optionally, find the sequence of choices that leads to the solution state from the initial problem state.
Given an initial problem state, find any solution state that can be reached from it by making a set of choices at each step. Optionally, find the sequence of choices that leads to the solution state from the initial problem state.
Liking the course? Check our discounted plans to continue learning.