Backtracking Algorithms




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).


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.



Recent Articles on Backtracking


Topics :



Standard Problems :












  1. Backtracking | Set 1 (The Knight?s tour problem)

  2. Backtracking | Set 2 (Rat in a Maze)

  3. Backtracking | Set 3 (N Queen Problem)

  4. Backtracking | Set 4 (Subset Sum)

  5. Backtracking | Set 5 (m Coloring Problem)

  6. Backtracking | Set 6 (Hamiltonian Cycle)

  7. Backtracking | Set 7 (Sudoku)

  8. Backtracking | Set 8 (Solving Cryptarithmetic Puzzles)

  9. Backtracking | Set 9 (Magnet Puzzle)

  10. N Queen in O(n) space

  11. Boggle | Set 2 (Using Trie)

  12. Remove Invalid Parentheses

  13. Prime numbers after prime P with sum S

  14. Rat in a Maze with multiple steps or jump allowed

  15. A backtracking approach to generate n bit Gray Codes

  16. C++ program for Solving Cryptarithmetic Puzzles

  17. Write a program to print all permutations of a given string

  18. Print all possible paths from top left to bottom right of a mXn matrix



Misc :




  1. Tug of War

  2. 8 queen problem

  3. Combinational Sum

  4. Backtracking to find all subsets

  5. Power Set in Lexicographic order

  6. Check if a given string is sum-string

  7. Fill 8 numbers in grid with given conditions

  8. Word Break Problem using Backtracking

  9. Minimize number of unique characters in string

  10. Count all possible paths between two vertices

  11. Partition of a set into K subsets with equal sum

  12. Warnsdorff?s algorithm for Knight?s tour problem

  13. Longest Possible Route in a Matrix with Hurdles

  14. Match a pattern and String without using regular expressions

  15. Fill two instances of all numbers from 1 to n in a specific way

  16. Find all distinct subsets of a given set

  17. Find shortest safe route in a path with landmines

  18. Find paths from corner cell to middle cell in maze

  19. Find if there is a path of more than k length from a source

  20. Find Maximum number possible by doing at-most K swaps

  21. Print all palindromic partitions of a string

  22. Printing all solutions in N-Queen Problem

  23. Print all paths from a given source to a destination

  24. Print all possible strings that can be made by placing spaces| Set-1

  25. Print all possible strings that can be made by placing spaces| Set-2

  26. Print all longest common sub-sequences in lexicographical order

  27. Smallest expression to represent a number using single digit

  28. Given an array A[] and a number x, check for pair in A[] with sum as x

  29. Combinations where every element appears twice and distance between appearances is equal to the value



Quick Links :



If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.ramthoughts.org or mail your article to contribute@ramthoughts.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.











My Personal Notes
arrow_drop_up