DSA - Backtracking Algorithm

The backtracking algorithm is a problem-solving approach that tries out all the possible solutions and chooses the best or desired ones. Generally, it is used to solve problems that have multiple solutions. The term backtracking suggests that for a given problem, if the current solution is not suitable, eliminate it and then backtrack to try other solutions.

When do we use backtracking algorithm?

Backtracking algorithm can be used for the following problems −

• The problem has multiple solutions or requires finding all possible solutions.

• When the given problem can be broken down into smaller subproblems that are similar to the original problem.

• If the problem has some constraints or rules that must be satisfied by the solution

How does backtracking algorithm work?

The backtracking algorithm explores various paths to find a sequence path that takes us to the solution. Along these paths, it establishes some small checkpoints from where the problem can backtrack if no feasible solution is found. This process continues until the best solution is found.

In the above figure, green is the start point, blue is the intermediate point, red are points with no feasible solution, grey is the end solution.

When backtracking algorithm reaches the end of the solution, it checks whether this path is a solution or not. If it is the solution path, it returns that otherwise, it backtracks to one step behind in order to find a solution.

Algorithm

Following is the algorithm for backtracking −

1. Start
2. if current_position is goal, return success.
3. else
4. if current_position is an end point, return failed.
5. else-if current_position is not end point, explore and repeat above steps.
6. Stop

Complexity of Backtracking

Generally, the time complexity of backtracking algorithm is exponential (0(kⁿ)). In some cases, it is observed that its time complexity is factorial (0(N!)).

Types of Backtracking Problem

The backtracking algorithm is applied to some specific types of problems. They are as follows −

• Decision problem − It is used to find a feasible solution of the problem.

• Optimization problem − It is used to find the best solution that can be applied.

• Enumeration problem− It is used to find the set of all feasible solutions of the problem.

Examples of Backtracking Algorithm

The following list shows examples of Backtracking Algorithm −

• Hamiltonian Cycle
• M-Coloring Problem
• N Queen Problem
• Rat in Maze Problem
• Cryptarithmetic Puzzle
• Subset Sum Problem
• Sudoku Solving Algorithm
• Knight-Tour Problem
• Tug-Of-War Problem
• Word Break Problem
• Maximum number by swapping problem