Backtracking
⏱ Time: O(2^N) or O(N!)💾 Space: O(N)
An algorithmic technique that considers searching every possible combination to solve a computational problem. It builds candidates incrementally and abandons (backtracks) a candidate as soon as it cannot lead to a valid solution.
🎯 When to Use
- ✓Generating all subsets, permutations, or combinations
- ✓Constraint satisfaction problems (Sudoku, N-Queens)
- ✓Exhaustive search with pruning
📝 Pseudocode
Backtracking TemplateO(2^N) or O(N!)
1function backtrack(candidate, state): 2 if isSolution(candidate): 3 output(candidate) 4 return 5 for choice in choices(state): 6 makeChoice(choice) 7 backtrack(candidate, state) 8 undoChoice(choice)
🏢 Real-World Use Cases
Uber
Multi-Stop Pool Routing
Finding valid passenger combination routes and pickup sequences using pruned combinatorial search.