Backtracking
Backtracking solves problems recursively by building a solution incrementally, one piece at a time and removing those solutions that fail to satisfy the constraints of the problem at any point of time.
Backtracking
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
Concepts and Problems - Backtracking
| # | Title | Difficulty | Companies |
|---|---|---|---|
1. | The idea of Exhaustive Search | ||
2. | Example 1 : Permutations | MEDIUM | Microsoft Adobe Google |
3. | The Idea of Backtracking | ||
4. | Example 1 : N Queen Problem | HARD | Amazon Facebook Qualcomm |