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

avatar
  Subscribe  
Notify of