Open In App

Backtracking Algorithm

Last Updated : 17 Apr, 2024
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

Backtracking algorithms are like problem-solving strategies that help explore different options to find the best solution. They work by trying out different paths and if one doesn't work, they backtrack and try another until they find the right one. It's like solving a puzzle by testing different pieces until they fit together perfectly.

Backtracking

Table of Content

What is Backtracking Algorithm?

Backtracking is a problem-solving algorithmic technique that involves finding a solution incrementally by trying different options and undoing them if they lead to a dead end.

It is commonly used in situations where you need to explore multiple possibilities to solve a problem, like searching for a path in a maze or solving puzzles like Sudoku. When a dead end is reached, the algorithm backtracks to the previous decision point and explores a different path until a solution is found or all possibilities have been exhausted.

How Does a Backtracking Algorithm Work?

A backtracking algorithm works by recursively exploring all possible solutions to a problem. It starts by choosing an initial solution, and then it explores all possible extensions of that solution. If an extension leads to a solution, the algorithm returns that solution. If an extension does not lead to a solution, the algorithm backtracks to the previous solution and tries a different extension.

The following is a general outline of how a backtracking algorithm works:

  1. Choose an initial solution.
  2. Explore all possible extensions of the current solution.
  3. If an extension leads to a solution, return that solution.
  4. If an extension does not lead to a solution, backtrack to the previous solution and try a different extension.
  5. Repeat steps 2-4 until all possible solutions have been explored.

Example of Backtracking Algorithm

Example: Finding the shortest path through a maze

Input: A maze represented as a 2D array, where 0 represents an open space and 1 represents a wall.

Algorithm:

  1. Start at the starting point.
  2. For each of the four possible directions (up, down, left, right), try moving in that direction.
  3. If moving in that direction leads to the ending point, return the path taken.
  4. If moving in that direction does not lead to the ending point, backtrack to the previous position and try a different direction.
  5. Repeat steps 2-4 until the ending point is reached or all possible paths have been explored.

When to Use a Backtracking Algorithm?

Backtracking algorithms are best used to solve problems that have the following characteristics:

  • There are multiple possible solutions to the problem.
  • The problem can be broken down into smaller subproblems.
  • The subproblems can be solved independently.

Applications of Backtracking Algorithm

Backtracking algorithms are used in a wide variety of applications, including:

  • Solving puzzles (e.g., Sudoku, crossword puzzles)
  • Finding the shortest path through a maze
  • Scheduling problems
  • Resource allocation problems
  • Network optimization problems

Basic of Backtracking Algorithm:

Standard Problems on Backtracking Algorithm:

Easy Problems on Backtracking Algorithm:

Medium Problems on Backtracking Algorithm:

Hard Problems on Backtracking Algorithm:

Quick Links :


H
harendrakumar123
News
Improve
Next Article
Introduction to Backtracking

Similar Reads

Backtracking Algorithm in Python
Backtracking is a problem-solving algorithmic technique that involves finding a solution incrementally by trying different options and undoing them if they lead to a dead end. The backtracking algorithm is a recursive algorithm that is used to solve problems by making a series of choices, and if a choice leads to a dead end, it backtracks to the la
4 min read
Top 20 Backtracking Algorithm Interview Questions
N Queens ProblemWarnsdorff's AlgorithmWord Break ProblemRemove Invalid ParenthesisMatch a pattern and string using regular expressionFind Path from corner cell to middle cell in a mazeHamiltonian cycleSudokuM Coloring ProblemRat in a MazePrint all permutations of a given stringCrptarithmetic puzzleFind if there is a path of more than k length from
1 min read
Algorithms | Backtracking | Question 1
Which of the following is not a backtracking algorithm? (A) Knight tour problem (B) N queen problem (C) Tower of hanoi (D) M coloring problem Answer: (C) Explanation: Knight tour problem, N Queen problem and M coloring problem involve backtracking. Tower of hanoi uses simple recursion.
1 min read
Print the DFS traversal step-wise (Backtracking also)
Given a graph, the task is to print the DFS traversal of a graph which includes every step including the backtracking. 1st step:- 0 -> 1 2nd step:- 1 -> 5 3rd step:- 5 -> 1 (backtracking step) 4th step:- 1 -> 6... and so on till all the nodes are visited. Dfs step-wise(including backtracking) is: 0 1 5 1 6 7 8 7 6 1 0 2 4 2 9 3 10 Note:
10 min read
Rat in a Maze | Backtracking using Stack
Prerequisites - Recursion, Backtracking and Stack Data Structure. A Maze is given as N*M binary matrix of blocks and there is a rat initially at (0, 0) ie. maze[0][0] and the rat wants to eat food which is present at some given block in the maze (fx, fy). In a maze matrix, 0 means that the block is a dead end and 1 means that the block can be used
15+ min read
Travelling Salesman Problem implementation using BackTracking
Travelling Salesman Problem (TSP): Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns back to the starting point.Note the difference between Hamiltonian Cycle and TSP. The Hamiltonian cycle problem is to find if there exist a tour that v
9 min read
Difference between Backtracking and Branch-N-Bound technique
Algorithms are the methodical sequence of steps which are defined to solve complex problems. In this article, we will see the difference between two such algorithms which are backtracking and branch and bound technique. Before getting into the differences, lets first understand each of these algorithms. Backtracking: Backtracking is a general algor
4 min read
Maximum size subset with given sum using Backtracking
Given an array arr[] consisting of N integers and an integer K, the task is to find the length of the longest subsequence with a sum equal to K.Examples: Input: arr[] = {-4, -2, -2, -1, 6}, K = 0 Output: 3 Explanation: The longest subsequence is of length 3 which is {-4, -2, 6} having sum 0.Input: arr[] = {-3, 0, 1, 1, 2}, K = 1 Output: 5 Explanati
9 min read
Generate all distinct subsequences of array using backtracking
Given an array arr[] consisting of N positive integers, the task is to generate all distinct subsequences of the array. Examples: Input: arr[] = {1, 2, 2}Output: {} {1} {1, 2} {1, 2, 2} {2} {2, 2}Explanation:The total subsequences of the given array are {}, {1}, {2}, {2}, {1, 2}, {1, 2}, {2, 2}, {1, 2, 2}.Since {2} and {1, 2} are repeated twice, pr
7 min read
What is the difference between Backtracking and Recursion?
What is Recursion? The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function. Properties of Recursion:Performing the same operations multiple times with different inputs.In every step, we try smaller inputs to make the problem smaller.A base condition is nee
2 min read
Backtracking meaning in DSA
Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem. Backtracking simple structure is shown like the following: Properties of Backtracking:Incremental construction: Backtracking builds a solution incrementally by constructing a partial solution
3 min read
Subset Sum Problem using Backtracking
Given a set[] of non-negative integers and a value sum, the task is to print the subset of the given set whose sum is equal to the given sum. Examples:  Input: set[] = {1,2,1}, sum = 3Output: [1,2],[2,1]Explanation: There are subsets [1,2],[2,1] with sum 3. Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30Output: []Explanation: There is no subset that
8 min read
Word Break Problem using Backtracking
Given a valid sentence without any spaces between the words and a dictionary of valid English words, find all possible ways to break the sentence into individual dictionary words. Example: Consider the following dictionary { i, like, sam, sung, samsung, mobile, ice, and, cream, icecream, man, go, mango} Input: "ilikesamsungmobile" Output: i like sa
8 min read
A backtracking approach to generate n bit Gray Codes
Given a number n, the task is to generate n bit Gray codes (generate bit patterns from 0 to 2^n-1 such that successive patterns differ by one bit) Examples: Input : 2 Output : 0 1 3 2Explanation : 00 - 001 - 111 - 310 - 2Input : 3 Output : 0 1 3 2 6 7 5 4 We have discussed an approach in Generate n-bit Gray CodesThis article provides a backtracking
6 min read
Print all Palindromic Partitions of a String using Backtracking
Given a string, find all possible palindromic partitions of given string. Note that this problem is different from Palindrome Partitioning Problem, there the task was to find the partitioning with minimum cuts in input string. Here we need to print all possible partitions. Example: Input: nitinOutput: n i t i n n iti n nitin Input: geeksOutput: g e
7 min read
Edge Relaxation Property for Dijkstra’s Algorithm and Bellman Ford's Algorithm
In the field of graph theory, various shortest path algorithms especially Dijkstra’s algorithm and Bellmann-Ford’s algorithm repeatedly employ the use of the technique called Edge Relaxation. The idea of relaxation is the same in both algorithms and it is by understanding, the 'Relaxation property' we can fully grasp the working of the two algorith
4 min read
Difference between Greedy Algorithm and Divide and Conquer Algorithm
Greedy algorithm and divide and conquer algorithm are two common algorithmic paradigms used to solve problems. The main difference between them lies in their approach to solving problems. Greedy Algorithm:The greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage wit
3 min read
Algorithm Library | C++ Magicians STL Algorithm
For all those who aspire to excel in competitive programming, only having a knowledge about containers of STL is of less use till one is not aware what all STL has to offer. STL has an ocean of algorithms, for all < algorithm > library functions : Refer here.Some of the most used algorithms on vectors and most useful one's in Competitive Prog
7 min read
What is the stupidest sorting algorithm? (Worst Sorting Algorithm)
Bogo sort stands out as the undisputed champion of stupidity. Unlike other sorting algorithms that follow a structured approach, Bogo sort relies on sheer luck and randomness to achieve its goal. How Bogo Sort Works?Bogo sort operates on the following principle: Randomly shuffle the elements in the list.Check if the list is sorted.If the list is no
2 min read
Difference Between Dijkstra's Algorithm and A* Search Algorithm
Dijkstra's Algorithm and A* Algorithm are two of the most widely used techniques. Both are employed to the find the shortest path between the nodes in a graph but they have distinct differences in their approaches and applications. Understanding these differences is crucial for the selecting the appropriate algorithm for the given problem. What is
3 min read
Z algorithm (Linear time pattern searching Algorithm)
This algorithm efficiently locates all instances of a specific pattern within a text in linear time. If the length of the text is "n" and the length of the pattern is "m," then the total time taken is O(m + n), with a linear auxiliary space. It is worth noting that the time and auxiliary space of this algorithm is the same as the KMP algorithm, but
13 min read
Karatsuba algorithm for fast multiplication using Divide and Conquer algorithm
Given two binary strings that represent value of two integers, find the product of two strings. For example, if the first bit string is "1100" and second bit string is "1010", output should be 120. For simplicity, let the length of two strings be same and be n. A Naive Approach is to follow the process we study in school. One by one take all bits o
15+ min read
Reversal algorithm for Array rotation
Given an array arr[] of size N, the task is to rotate the array by d position to the left. Examples: Input: arr[] = {1, 2, 3, 4, 5, 6, 7}, d = 2Output: 3, 4, 5, 6, 7, 1, 2Explanation: If the array is rotated by 1 position to the left, it becomes {2, 3, 4, 5, 6, 7, 1}.When it is rotated further by 1 position,it becomes: {3, 4, 5, 6, 7, 1, 2} Input:
15 min read
Block swap algorithm for array rotation
Write a function rotate(arr[], d, n) that rotates arr[] of size n by d elements. Rotation of the above array by 2 will make an array Algorithm : Initialize A = arr[0..d-1] and B = arr[d..n-1] 1) Do following until size of A is equal to size of B a) If A is shorter, divide B into Bl and Br such that Br is of same length as A. Swap A and Br to change
15+ min read
Boruvka's algorithm for Minimum Spanning Tree
Following two algorithms are generally taught for Minimum Spanning Tree (MST) problem. Prim's algorithm Kruskal's algorithm There is a third algorithm called Boruvka's algorithm for MST which (like the above two) is also Greedy algorithm. The Boruvka's algorithm is the oldest minimum spanning tree algorithm was discovered by Boruvka in 1926, long b
1 min read
Introduction to Push Relabel Algorithm
Given a graph which represents a flow network where every edge has a capacity. Also given two vertices source ‘s’ and sink ‘t’ in the graph, find the maximum possible flow from s to t with following constraints: Flow on an edge doesn’t exceed the given capacity of the edge. Incoming flow is equal to outgoing flow for every vertex except s and t. Fo
6 min read
An in-place algorithm for String Transformation
Given a string, move all even positioned elements to the end of the string. While moving elements, keep the relative order of all even positioned and odd positioned elements the same. For example, if the given string is "a1b2c3d4e5f6g7h8i9j1k2l3m4", convert it to "abcdefghijklm1234567891234" in-place and in O(n) time complexity. Below are the steps
15+ min read
Union By Rank and Path Compression in Union-Find Algorithm
In the previous post, we introduced union find algorithm and used it to detect cycles in a graph. We used the following union() and find() operations for subsets. C/C++ Code // Naive implementation of find int find(int parent[], int i) { if (parent[i] == -1) return i; return find(parent, parent[i]); } // Naive implementation of union() void Union(i
15+ min read
Closest Pair of Points using Divide and Conquer algorithm
We are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array. This problem arises in a number of applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision. Recall the following formula for dist
15+ min read
Fleury's Algorithm for printing Eulerian Path or Circuit
Eulerian Path is a path in a graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path that starts and ends on the same vertex. We strongly recommend first reading the following post on Euler Path and Circuit. "https://www.cdn.geeksforgeeks.org/eulerian-path-and-circuit/" In the above-mentioned post, we discussed the problem o
15+ min read
Article Tags :
Practice Tags :
three90RightbarBannerImg
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox