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 :
- Decision Problem : Search for a feasible solution
- Optimisation Problem : Search for the best solution
- Enumeration Problem : Find all feasible solutions
