Backtracking: Practice Problems and Interview Questions

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.