Backtracking is essentially brute forcing a problem. Conceptually, one can imagine the procedure of backtracking as a tree traversal on a decision tree - we take a path towards a solution and then "back track" and try another path in the tree as soon as we determine that the current path cannot lead to a valid solution or we reach a base case.
Almost the same as DFS but we have the backtrack step.
Tips for identifying backtracking:
- Question says "generate all"
- You need to search all paths for a solution.
Most back tracking questions have the same boiler plate:
1. Base cases
2. Add choice to solution
3. Recurse
4. Undo/Revert choice from solution (backtrack)
Common pitfalls:
- Ensuring you “undo” the state correctly on each backtrack.
- Not handling base case. when do we stop the recursion? When do we add to our array?
- Can sometimes presort to help cut off branches early.
- Handling duplicates? Handled by skipping over duplicate choices in the recursion.
________________________________________________________
00:00 - Backtracking Explained
04:15 - Q1 - Generating all subsets
15:52 - Q2 - Word Search
31:27 - Common Pitfalls
