codaBack to Academy
patterns
Backtracking
Backtracking systematically explores all possible solutions by building candidates incrementally and abandoning a path as soon as it determines the candidate cannot lead to a valid solution. It uses recursion to try each option, undo the choice (backtrack), and try the next, effectively pruning the search space compared to brute force.
Use Cases
- •Generating all subsets, permutations, and combinations
- •Solving constraint satisfaction problems like Sudoku and N-Queens
- •Finding all paths in a maze or grid
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(n!) | O(n!) | O(n!) |
| Space | O(n) | ||
Visualization
Subsets:[]
Implementation
Output
Click "Run Code" to see output...