# Introduction to Backtracking

Let’s go over the Backtracking pattern, its real-world applications, and some problems we can solve with it.

## We'll cover the following

## About the pattern

Imagine we’re planning an exciting road trip through a city, aiming to visit all the places we want to see while covering the shortest distance possible. However, there are some conditions we must follow: we can’t revisit the same place more than once, and we must end up back where we started. This problem, known as the city road trip problem, requires finding the optimal route that satisfies these conditions. It’s a classic example where the concept of backtracking comes into play, allowing us to explore different paths until we find the shortest one that fulfills all the conditions.

Let’s first see how this problem can be solved using a brute-force approach. We can do this by exploring routes in every single way we can visit the places. We have to write down every possible route, check how long each one is, and then pick the shortest one. But as our list of places grows, it makes this approach computationally impractical for a large number of routes.

Now, let’s look at a backtracking approach to solve the same problem. With backtracking, we can start by picking a place and choose the next place to visit that’s close and follows our conditions. We move back (backtrack) to the previous place if the current place has been visited before or if we cannot move forward to any place from here. We check these conditions on each of our choices because we do not want to break any of our road trip rules. We keep doing this, choosing, checking conditions, and backtracking until we’ve visited all the places according to the requirements. At every step, we choose the closest place, ensuring we have chosen the shortest path to visit all the places we want to see.

**Backtracking** is an algorithmic technique for solving problems by incrementally constructing choices to the solutions. We abandon choices as soon as it is determined that the choice cannot lead to a feasible solution. On the other side, brute-force approaches attempt to evaluate all possible solutions to select the required one. Backtracking avoids the computational cost of generating and testing all possible solutions. This makes backtracking a more efficient approach. Backtracking also offers efficiency improvements over brute-force methods by applying constraints at each step to prune non-viable paths.

As seen in the above example, backtracking works by exploring all potential routes toward a solution step-by-step. It can be visualized as traversing a

Let’s look at the visualization of the space state tree below to better understand the working:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.