Backtracking Algorithm Explained With Examples

The Backtracking algorithm is a problem-solving algorithm, which uses recursion at its core. It involves trying to build a solution incrementally piece by piece. And solutions that don’t satisfy the conditions are removed during the course of program execution. It uses a brute force approach while trying to find a solution to the problem. Basically, all the possible combinations and solutions are tried. And those solutions that don’t fulfill the criteria are removed or rejected.

It is one of the most widely used problem-solving algorithms for questions where all possible solutions need to be found. The DFS (Depth First Search) technique is used in a typical backtracking algorithm. The DFS algorithm is an algorithm that goes into one path to its entirety before going to the next option. If there are options A, B, & C in step 1, Depth First Search explores option A in its entirety before exploring options B & C.

But just because it uses a brute force approach does not mean it will not work well for optimization problems. As in some cases, the backtracking algorithm has been found to be very useful for optimization problems too.

State-Space Tree (Used In The Backtracking Algorithm)

A state-space tree is generally used to represent all the states or the solutions that are possible for a particular problem. A state-space tree is a tree that has an initial state at the root and the final state or terminal state at the leaf nodes.

Let’s take a simple example and see what the state-space tree looks like for this particular example. The example we’ll consider here will have three numbers as input. The goal is to generate all possible combinations of the numbers. So if we have the numbers 1, 2, & 3 as inputs, the output should contain the numbers 123, 132, 213, 231, 312, and 321. Now let’s look at the state-space tree for this example.

Backtracking Algorithm
Figure 1: Combination

If we start from the top and go to the bottom, we have the outputs as 123, 132, 213, 231, 312, and 321.

Now suppose we add one condition to the problem. And the condition is that the numbers 1 & 2 cannot be adjacent to one another. In that case, the outputs 123, 213, 312, & 321 will be automatically rejected or eliminated from the output. And all that remains in the final output will be 132 & 231. How will the state-space tree look now? Let’s have a look.

Backtracking Algorithm
Figure 2: Combination with conditions

If you look at the above picture, whenever we encounter a situation where 1 & 2 are adjacent to one another, we discard the state and backtrack to the previous state and check again from there. We don’t go any further once we encounter a situation that violates the conditions.

Also check: How to Prepare for and Crack the Coding Interview

Backtracking Algorithm Steps

Let’s look at the steps involved in the backtracking algorithm.

  1. If the current state is the answer/ result, return SUCCESS.
  2. ELSE
  3. If the current state is the endpoint/ invalid, return FAILED.
  4. ELSE IF, the current state is not the endpoint/ invalid, repeat the above steps for the next input.

The backtracking algorithm involves recursion and recursive calls at its core. Let’s look at how the recursive call is made.

  1. Do something – This action can be something like adding a value to a list or adding a character to a string.
  2. Make a recursive call – This recursive call will usually be for the next set of inputs that should be considered for processing.
  3. Undo what was done in Step 1 – This will undo the additions done in step 1. And it can be something like removing the last element from the list or removing the last character from the string.

The last step of undoing step 1 is very important in the backtracking algorithm. In the above example, have a look at figure 2. We add 1 in the first step & 2 in the second step. Then, we see that this violates our condition of not having 1 & 2 adjacent to each other. Here, we backtrack and undo what we did earlier by removing 2 and then we add 3 in its place and move forward from there.

Sample Code

The below code is for the Permutations problem. As seen in the code below, the above steps of doing something, making a recursive call, and undoing what was done in step one are clearly shown. Although this is the general format of code in the backtracking algorithm, it is not always the case. The code might slightly vary depending on the problem.

    	for(int i = 0; i < nums.length; i++) {
    		if(!list.contains(nums[i])) {
    			list.add(nums[i]);           // 1. Do something
    			recursion(ans, nums, list);  // 2. Make a recursive call
    			list.remove(list.size() -1); // 3. Undo what was done in Step 1

When Should Backtracking Algorithm Be Used?

The Backtracking algorithm is used in a variety of problems and situations. We’ll have a look at some of these below:

  • It is generally used to find all the possible solutions to a given problem. Since it uses the brute-force approach to finding the solution to the problem, it is suitable for finding all solutions to a particular problem. These types of problems are also known as enumeration problems.
  • It can be used in a decision problem to find a feasible solution to the problem.
  • The backtracking algorithm can be used for an optimization problem where the goal is to find the best solution among a host of solutions.

However, it is not an optimized algorithm because it uses the brute-force approach at its core. So if time complexity is a constraint, it is advisable to use some other optimized algorithm that might be better suited for that case.

Backtracking Algorithm Example

Let’s solve a simple problem and look at how the backtracking algorithm works. We will take the N-Queens problem as an example and try to solve it using the backtracking algorithm to see how it works. The N-Queens problem states that if you have an N * N board, you have to place N queens on the board such that no two queens attack each other. A queen is said to attack another queen if it’s in the same row, the same column, or the same diagonal. For simplicity purposes, let’s take a 4 * 4 board and try to place 4 queens on the board such that no two queens attack each other. For a 4 * 4 board, we will have two possible solutions. They are as below.

If you look at the above two solutions, no two queens are attacking each other. And if you consider a bigger board, there will be many more solutions. For example, if you consider a 5 * 5 board, we will have 10 possible solutions. And so on.

Also check: How to crack technical interview – Google, Amazon & more

N-Queens Problem Execution Steps

Looking at the solutions above, it is not clear how we arrived at the above solutions. So let’s list down the steps one by one and see how we reach the final solution.

Step 1

Place queen 1 at a position such that it is not being attacked. Since there are no queens positioned anywhere on the board, we can place queen 1 anywhere.

Backtracking Algorithm

Step 2

Now, place queen 2 at a position such that it is not being attacked.

N-Queens Problem

Step 3

If you carefully look at the figure above, you will see that we cannot place queen 3 in the third row without it being attacked by the other two queens. And this is where the magic of the backtracking algorithm comes into play. We go back one step and check if we can change anything there to get to the solution. So, we backtrack and change the position of queen 2 such that it’s not being attacked by any other queen.

Backtracking Algorithm

Step 4

Place queen 3 at a position such that it is not being attacked.

N-Queens Problem

Step 5

If you look at the above figure, you will notice that we cannot place queen 4 anywhere in the fourth row without it being attacked by the other three queens. So backtrack and try to change the position of queen 3. But queen 3 has run out of options. And we cannot place queen 3 anywhere else without it being attacked by the other two queens. Again backtrack and try to change the position of queen 2. But queen 2 has also run out of options. So backtrack again and change the position of queen 1. And you should keep going like this till you reach a step where you have other options available.

Backtracking Algorithm

Step 6

Place queen 2 at a position such that it is not being attacked.

N-Queens Problem

Step 7

Now, place queen 3 at a position such that it is not being attacked.

Backtracking Algorithm

Step 8

Finally, place queen 4 at a position such that it is not being attacked.

N-Queens Problem

And you have reached one of the solutions in figure 3. Similarly, you can reach the other solution as well if you keep on backtracking further.

Important Problems Based on The Backtracking Algorithm

There are a lot of problems that can be solved using the backtracking algorithm. Some of the important problems based on the backtracking algorithm have been mentioned below. And the names of the companies these questions were asked in are included in brackets.

Please try to solve some of these problems. Because practicing on your own is the only way to improve your understanding of the backtracking algorithm.

That’s all on the Backtracking algorithm.

To keep yourself up to date with our latest content, please subscribe to our newsletter by dropping your email address here: Signup for Our Newsletter.

Please follow us on Medium.

Further Reading

Leave a Reply

Your email address will not be published. Required fields are marked *