Backtracking Algorithms

DSA for Beginners
Learn more about Backtracking Algorithms in DSA Self Paced Course
Practice Problems on Backtracking Algorithms
Top Quizzes on Backtracking Algorithms

What is Backtracking?

Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem.

What is Backtracking Algorithm?

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time (by time, here, is referred to the time elapsed till reaching any level of the search tree).

Types of Backtracking Algorithm

There are three types of problems in backtracking

1. Decision Problem – In this, we search for a feasible solution.
2. Optimization Problem – In this, we search for the best solution.
3. Enumeration Problem – In this, we find all feasible solutions.

When can be Backtracking Algorithm used?

For example, consider the SudoKo solving Problem, we try filling digits one by one. Whenever we find that current digit cannot lead to a solution, we remove it (backtrack) and try next digit. This is better than naive approach (generating all possible combinations of digits and then trying every combination one by one) as it drops a set of permutations whenever it backtracks.

Topics :

Introduction:

1. Introduction to Backtracking – Data Structure and Algorithm Tutorials
2. Difference between Backtracking and Branch-N-Bound technique
3. What is the difference between Backtracking and Recursion?

Standard Problems on Backtracking:

1. The Knight’s tour problem
2. Rat in a Maze
3. N Queen Problem | Backtracking-3
4. Subset Sum problem
5. m Coloring Problem
6. Hamiltonian Cycle
7. Sudoku | Backtracking-7
8. Magnet Puzzle
9. Remove Invalid Parentheses
10. A backtracking approach to generate n bit Gray Codes
11. Write a program to print all permutations of a given string

Some Practice problems on Backtracking:

• Easy:
  1. Backtracking to find all subsets
  2. Check if a given string is sum-string
  3. Count all possible paths between two vertices
  4. Find all distinct subsets of a given set
  5. Find if there is a path of more than k length from a source
  6. Print all paths from a given source to a destination
  7. Print all possible strings that can be made by placing spaces
• Medium:
  1. Tug of War
  2. 8 queen problem
  3. Combinational Sum
  4. Warnsdorff’s algorithm for Knight’s tour problem
  5. Find paths from corner cell to middle cell in maze
  6. Find Maximum number possible by doing at-most K swaps
  7. Rat in a Maze with multiple steps or jump allowed
  8. N Queen in O(n) space
• Hard:
  1. Power Set in Lexicographic order
  2. Word Break Problem using Backtracking
  3. Partition of a set into K subsets with equal sum
  4. Longest Possible Route in a Matrix with Hurdles
  5. Find shortest safe route in a path with landmines
  6. Print all palindromic partitions of a string
  7. Printing all solutions in N-Queen Problem
  8. Print all longest common sub-sequences in lexicographical order

Quick Links :

• Learn Data Structure and Algorithms | DSA Tutorial
• Top 20 Backtracking Algorithm Interview Questions
• ‘Practice Problems’ on Backtracking
• ‘Quiz’ on Backtracking
• ‘Videos’ on Backtracking

If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.