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 which admit the concept of a “partial candidate solution” and a relatively quick test of whether it can possibly be completed to a valid solution. Backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test.

In this post, we have list out common problems that can be solved using backtracking technique –


  1. Print all possible solutions to N Queens problem
  2. Print all Possible Knight’s Tours in a chessboard
  3. Find Shortest Path in Maze
  4. Find Longest Possible Route in a Matrix
  5. Find path from source to destination in a matrix that satisfies given constraints
  6. Find total number of unique paths in a maze from source to destination
  7. Print All Hamiltonian Path present in a graph
  8. Print all k-colorable configurations of the graph (Vertex coloring of graph)
  9. Find all Permutations of a given string
  10. All combinations of elements satisfying given constraints
  11. Find all binary strings that can be formed from given wildcard pattern
  12. K-Partition Problem | Printing all Partitions
  13. Magnet Puzzle
  14. Find ways to calculate a target from elements of specified array
  15. Find minimum number possible by doing at-most K swaps
  16. Determine if a pattern matches with a string or not


Thank you for being with us. 🙂


Leave a Reply

Notify of