Backtracking: Practice Problems and Interview Questions

Vivek Srivastava
Techie Delight

--

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate `c` (“backtracks”) as soon as it determines that `c` cannot possibly be completed to a valid solution.

Backtracking can be applied only for problems that admit the concept of a “partial candidate solution” and a relatively quick test of whether it can be completed to a valid solution. Backtracking is often much faster than brute force enumeration of all candidates since it can eliminate a large number of candidates with a single test.

In this post, we have listed out common problems that can be solved using the backtracking technique:

  1. Print all possible solutions to N–Queens problem
  2. Print all possible Knight’s tours on a chessboard
  3. Find the shortest path in a maze
  4. Find the longest possible route in a matrix
  5. Find the path from source to destination in a matrix that satisfies given constraints
  6. Find the total number of unique paths in a maze from source to destination
  7. Find all combinations of elements satisfying given constraints
  8. K–Partition Problem | Printing all partitions
  9. Magnet Puzzle
  10. Print all k–colorable configurations of a graph (Vertex coloring of a graph)
  11. Find the minimum number possible by doing at-most `k` swaps
  12. Find all permutations of a string — C++, Java, Python
  13. Determine whether a string matches with a given pattern
  14. Find all paths from the first cell to the last cell of a matrix
  15. Print all shortest routes in a rectangular grid
  16. Find all distinct combinations of a given length with repetition allowed
  17. Print all combinations of numbers from 1 to `n` having sum `n`
  18. Print all triplets in an array with a sum less than or equal to a given number
  19. Find all possible combinations by replacing given digits with characters of the corresponding list
  20. Find all combinations of non-overlapping substrings of a string
  21. Find all n-digit numbers with equal sum of digits at even and odd indices
  22. Find all occurrences of the given string in a character matrix
  23. Print all distinct subsets of a given set
  24. Find all binary strings that can be formed from a wildcard pattern
  25. Find ways to calculate a target from elements of the specified array
  26. Find all Possible Topological Orderings of a DAG
  27. Print all Hamiltonian paths present in a graph
  28. Find the path between given vertices in a directed graph
  29. Generate a list of possible words from a character matrix
  30. Print all paths from the root to leaf nodes of a binary tree
  31. Print all paths from leaf to root node of a binary tree
  32. Generate the power set of a given set

Thank You.

--

--