Backtracking
Overview
Backtracking is an advanced algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, and removing (backtracking) those solutions that fail to satisfy the constraints of the problem. It is basically an optimized brute-force. Think of navigating a maze: you walk down a path until you hit a dead end, then you walk back to the last intersection and try a different path.
Syntax
The magic happens at the 'UN-CHOOSE' step. By removing the element we just added, we restore the `current` list to its previous state, allowing the `for` loop to try the next available number.
public void generatePermutations(int[] nums, List<Integer> current, List<List<Integer>> result) {
// 1. GOAL/BASE CASE: We built a valid combination!
if (current.size() == nums.length) {
result.add(new ArrayList<>(current)); // Save a COPY of the state
return;
}
// 2. EXPLORE: Try every possible option
for (int i = 0; i < nums.length; i++) {
// Skip invalid choices (already used)
if (current.contains(nums[i])) continue;
// CHOOSE: Add to our current state
current.add(nums[i]);
// EXPLORE: Recursively build the rest
generatePermutations(nums, current, result);
// UN-CHOOSE (BACKTRACK): Remove the last choice to try the next one
current.remove(current.size() - 1);
}
}Common Pitfalls
- Forgetting to completely undo the state (Backtrack). If you modify global variables or arrays during the 'CHOOSE' phase, you MUST revert them.
- Not optimizing the 'isValid' check. If checking whether a choice is valid takes O(N) time, your already slow Backtracking algorithm becomes incredibly slow.
Interview Tips
- Backtracking is essentially optimized brute-force. It builds a state, checks if it's valid, and if not, UNDOES the last step to try another path.
Real-World Example
Backtracking is heavily used in scheduling software, solving Sudoku puzzles, and calculating optimized routing for delivery drivers (Travelling Salesman Problem).
public boolean solveSudoku(char[][] board) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (board[row][col] == '.') {
// Try numbers 1 through 9
for (char num = '1'; num <= '9'; num++) {
if (isValidPlacement(board, row, col, num)) {
board[row][col] = num; // CHOOSE
if (solveSudoku(board)) return true; // EXPLORE
board[row][col] = '.'; // BACKTRACK
}
}
return false; // Dead end, go back!
}
}
}
return true; // Board is full
}