Backtracking is an effective technique for solving algorithmic problems during interviews.

Critical steps in backtracking solution :

  • Construct a partial solution
  • Verify if the partial solution is valid or invalid
  • Verify if the solution is complete

How to determine if a problem can be solved using Backtracking? Every constraint satisfaction problem which has well-defined constraints can be solved by Backtracking. There are three types of problems which can be solved using backtracking :

  1. Decision Problem : Search for a feasible solution
  2. Optimisation Problem : Search for the best solution
  3. Enumeration Problem : Find all feasible solutions