Backtracking – Interview Questions and Practice Problems

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 problemHard
2. Print all possible Knight’s tours on a chessboardHard
3. Find the shortest path in a mazeMedium
4. Find the longest possible route in a matrixMedium
5. Find the path from source to destination in a matrix that satisfies given constraintsMedium
6. Find the total number of unique paths in a maze from source to destinationMedium
7. Find all combinations of elements satisfying given constraintsMedium
8. K–Partition Problem | Printing all partitionsHard
9. Magnet PuzzleHard
10. Print all k–colorable configurations of a graph (Vertex coloring of a graph)Medium
11. Find the minimum number possible by doing at-most k swapsMedium
12. Find all permutations of a string – C++, Java, PythonHard
13. Determine whether a string matches with a given patternHard
14. Find all paths from the first cell to the last cell of a matrixMedium
15. Print all shortest routes in a rectangular gridMedium
16. Find all distinct combinations of a given length with repetition allowedMedium
17. Print all combinations of numbers from 1 to n having sum nMedium
18. Print all triplets in an array with a sum less than or equal to a given numberMedium
19. Find all possible combinations by replacing given digits with characters of the corresponding listHard
20. Find all combinations of non-overlapping substrings of a stringMedium
21. Find all n-digit numbers with equal sum of digits at even and odd indicesHard
22. Find all occurrences of the given string in a character matrixHard
23. Print all distinct subsets of a given setHard
24. Find all binary strings that can be formed from a wildcard patternMedium
25. Find ways to calculate a target from elements of the specified arrayMedium
26. Find all Possible Topological Orderings of a DAGHard
27. Print all Hamiltonian paths present in a graphHard
28. Find the path between given vertices in a directed graphEasy
29. Generate a list of possible words from a character matrixHard
30. Print all paths from the root to leaf nodes of a binary treeEasy
31. Print all paths from leaf to root node of a binary treeMedium
32. Generate the power set of a given setMedium