Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Backtracking?
2.1.
Sample Example
3.
Types of Backtracking
4.
Pseudo Code for Backtracking
4.1.
Backtracking vs Brute-force Approach
4.2.
Backtracking vs Recursion
5.
How to decide when to use Backtracking?
6.
Frequently Asked Questions
6.1.
What is Backtracking?
6.2.
When is backtracking used?
6.3.
Difference b/w recursion and backtracking?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Introduction To Backtracking

Author Neha Chauhan
2 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

There are many Problem Solving Strategies like the Brute-force approach, dynamic programming approach, and recursive approach. One such strategy is the Backtracking approach. Backtracking can be defined as a strategy that, searches for every possible technique to solve a problem, abandoning a technique if it does not seem to give a feasible solution.

introduction to backtracking

In this article, we will give an introduction to Backtracking.

What is Backtracking?

Backtracking is a problem-solving strategy for finding all the solutions to a problem, by rejecting the solutions that do not satisfy the given constraint. In Backtracking, we pick a path and start solving the problem along that path. At any point in time, if we find that the path is leading to an invalid solution, we stop moving along that path and return back to explore other paths.

Sample Example

We want to find different ways in which three shapes (a diamond, a square and a triangle) can be arranged in a sequence, given the triangle should never be in the middle.

All the possibilities are:

Diamond, SquareTriangle.

SquareDiamondTriangle

TriangleDiamondSquare

TriangleSquareDiamond


The state space tree is shown below:

example of backtracking

Say we choose the diamond to be the first in the sequence. We will have two options for the second place - a square and a triangle. If we choose the square as the second element then the third element will be the triangle. As this sequence obeys the constraint, we accept it as a valid solution. We cannot choose the triangle as the second element, so we abandon this solution.

In the above example, we backtracked when we encountered a situation (the triangle as the second element) that did not satisfy our condition (the triangle should not be the middle element). 

There is a similar problem - Identify various permutations of a string that can help in understanding the problem and its solution in detail. 

We can make some observations about Backtracking from the above example: 

1️⃣ The problem must have a constraint.

2️⃣ The problem might have more than one solution.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Types of Backtracking

Types

Backtracking tries to search each and every possible combination of solutions at each step to solve.

We have three different types of classic problems in backtracking, which are as follows:

  • Enumeration problems:- In these kinds of problems, we tend to find all the feasible solutions.
  • Decision problems:- In these kinds of problems, we tend to find one feasible solution.
  • Optimization problems:- In these kinds of problems, we tend to find the best-optimized solution

Pseudo Code for Backtracking

Recursive Code

void exploreSolutions(n, params) :
    if (found a solution) :
        totalSolutions = totalSolutions + 1;
        displaySolution();
        if (totalSolutions >= solutionTarget) : 
            System.exit(0);
        return true;

    for (val in array of possibilities) :
        if (doesSatisfyConstraints(val, n, params)) :
            appendValue(val, n);
            bool result = exploreSolutions(n + 1, params);
	if (result == false)
            	removeValue(val, n);
    return false;

 

Finding whether a solution exists or not

boolean checkSolution(n, params) :
    if (found a solution) :
        displaySolution();
        return true;

    for (val in array of possibilities) :
        if (doesSatisfyConstraints(val, n)) :
            appendValue(val, n);
            if (findSolutions(n+1, other params) is true)
                return true;
            removeValue(val, n);
     return false;
example

Backtracking vs Brute-force Approach

Do not confuse Backtracking with the Brute-force approach. In the Brute-force approach, we explore all the options till the end, after which we check if the final answer is the desired solution. In Backtracking, we stop exploring an option mid-way if we find out that this option will not give a feasible solution. In Backtracking, we do not go all the way to the end to reject an option which saves us a lot of time. 

Backtracking is often faster than the brute force approach as it does not require generating and testing all possible solutions. Instead, it can eliminate a large number of candidates with a single test.

For the Sudoku solving problem, we can use the brute force approach and generate all possible combinations of numbers and then try every combination one by one. This will be time-consuming. Instead, we can use Backtracking, we try each digit one by one and if we find that the digit cannot give a solution we backtrack by removing it and trying the next digit, which allows us to drop some of the permutations. Hence, Backtracking is better than Brute-force.

Backtracking vs Recursion

The process of exploring all the options is done via recursion but Backtracking is just a form of recursion. It is different from a Recursive Approach. In Recursion, until we reach a base case we keep calling the function. Whereas, in Backtracking, we keep exploring the options until the best solution is obtained. 

To know more please refer to this article - Backtracking and Recursion.

Must Read Recursion in Data Structure

How to decide when to use Backtracking?

when to use backtracking

You can use Backtracking if there is a constraint that determines the outcome or if you want to find all of the possible outcomes of a problem. It can also be used to solve some optimization problems in which we abandon an option as soon as we determine, it does not lead to a solution.

A classic problem to understand Backtracking is the N-Queens problem. We recommend you to go through it.

If you want to read more articles we recommend you these articles:

🔥 Knight’s Tour Problem

🔥 Min Max Algorithm

🔥  N Queens

🔥 Sudoku Solver

🔥  Generate Parentheses

🔥 Word Break Problem 

🔥 Tug of War

🔥 Additive Numbers

🔥 Subsets

🔥 Print Permutations of all Strings 

🔥 Permutations of Array without Duplicates

🔥 Prime Number generator 

🔥 8 Queens Problem Using Backtracking

🔥Permutation of string

Frequently Asked Questions

What is Backtracking?

Backtracking is a problem-solving strategy for finding all the solutions to a problem, by rejecting the solutions that do not satisfy the given constraint

When is backtracking used?

It is generally used in problems where you have multiple options and after choosing one option, you have a set of new options hence recursion. The process continues until a final state or the desired state is reached.

Difference b/w recursion and backtracking?

Recursion and Backtracking both are nearly similar because both call their own function again and again, but the only difference between both of them is that in recursion, the function calls stops when it satisfies the base case, whereas, in backtracking, recursion is used to check and find all possible combinations until and unless we get the best solution for that problem.

Conclusion

Congratulations🎉on finishing the article. In this article, we discussed what backtracking is with the help of an example. We also discussed how backtracking is different from brute force and recursion. 

Now, that we have understood what Backtracking is, we encourage you to solve some of the backtracking problems -

🔥 Rat in a maze

🔥 Print Permutations of a string

          🔥 Valid Sudoku

🔥 Permutations


Head to the Guided Path on the Coding Ninjas Studio and upskill in Data Structures and AlgorithmsCompetitive ProgrammingSystem Design, and many more courses.

If you want to Practice top Coding Problems, attempt mock tests, or read interview experiences, head to the Coding Ninjas Studio, our practice platform.

We wish you Good Luck!🎈 Please upvote our blog 🏆 and help other ninjas grow.

Next article
Backtracking The Knight’s Tour Problem
Live masterclass