Backtracking Pattern
What is Backtracking?
Backtracking is an algorithmic technique that builds a solution incrementally, abandoning a candidate ("backtracking") as soon as it determines that the candidate cannot lead to a valid solution.
It's essentially a depth-first search of the solution space, where we explore all possible paths and backtrack when we hit a dead end.
When to Use Backtracking
Backtracking is useful when:
- You need to find all (or some) solutions to a problem
- The problem can be broken down into a sequence of decisions
- Each decision leads to a new subproblem
- You can determine if a partial solution can lead to a valid complete solution
Backtracking Template
- Define a recursive function that takes the current state and remaining choices
- Check if the current state is a valid solution (base case)
- For each possible choice:
- Make the choice (modify the current state)
- Recursively explore the resulting state
- Undo the choice (backtrack) to try other choices
Example: N-Queens Problem
The N-Queens problem asks how to place N queens on an N×N chessboard so that no two queens threaten each other.
Example: Permutations
Generate all possible permutations of a given array of distinct integers.
Time and Space Complexity
Time Complexity:
O(b^d), where b is the branching factor (number of choices at each step) and d is the maximum depth of the recursion.
Space Complexity:
O(d), where d is the maximum depth of the recursion, due to the recursion stack.
Pattern 1: Backtracking
Learn how to use DFS to solve problems by trying different possibilities and backtracking when a solution is not feasible.
What is Backtracking?
Backtracking is an algorithmic technique that builds a solution incrementally, abandoning a candidate ("backtracking") as soon as it determines that the candidate cannot lead to a valid solution.
It's essentially a depth-first search of the solution space, where we explore all possible paths and backtrack when we hit a dead end.
Key Insight: Backtracking is about exploring all possible solutions in a systematic way, while pruning branches that cannot lead to valid solutions as early as possible.
When to Use Backtracking
Combinatorial Problems
When you need to find all (or some) solutions to a problem with a large number of possible combinations, such as permutations, combinations, or subsets.
Constraint Satisfaction
When you need to find solutions that satisfy certain constraints, such as puzzles (Sudoku, crosswords), scheduling problems, or resource allocation.
Decision Problems
When you need to make a sequence of decisions, where each decision affects the available choices for future decisions, such as game playing or path finding.
The Backtracking Template
1Define the Problem
Define the problem in terms of decisions to be made, constraints to be satisfied, and the goal to be achieved.
2Recursive Function
Define a recursive function that takes the current state and remaining choices. Check if the current state is a valid solution (base case).
3Explore and Backtrack
For each possible choice: make the choice, recursively explore the resulting state, and then undo the choice (backtrack) to try other choices.
Pseudocode Template:
function backtrack(state, choices):
if isValidSolution(state):
addToResult(state)
return
for choice in choices:
if isValid(state, choice):
makeChoice(state, choice)
backtrack(state, remainingChoices)
undoChoice(state, choice) // Backtrack
Example: N-Queens Problem
The N-Queens problem asks how to place N queens on an N×N chessboard so that no two queens threaten each other. This is a classic backtracking problem.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576function solveNQueens(n) { // Result array to store all valid board configurations const result = []; // Initialize an empty board const board = Array(n).fill().map(() => Array(n).fill('.')); // Helper function to check if a queen can be placed at board[row][col] function isSafe(row, col) { // Check the column for (let i = 0; i < row; i++) { if (board[i][col] === 'Q') { return false; } } // Check upper-left diagonal for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] === 'Q') { return false; } } // Check upper-right diagonal for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (board[i][j] === 'Q') { return false; } } return true; } // Helper function to convert the board to the required format function addSolution() { const solution = board.map(row => row.join('')); result.push(solution); } // Backtracking function to place queens row by row function backtrack(row) { // If all queens are placed, add the solution if (row === n) { addSolution(); return; } // Try placing a queen in each column of the current row for (let col = 0; col < n; col++) { // If it's safe to place a queen at board[row][col] if (isSafe(row, col)) { // Place the queen board[row][col] = 'Q'; // Recursively place queens in the next row backtrack(row + 1); // Backtrack: remove the queen to try other positions board[row][col] = '.'; } } } // Start the backtracking from the first row backtrack(0); return result;} // Example usage:const solutions = solveNQueens(4);console.log(solutions);// Output: [// [".Q..", "...Q", "Q...", "..Q."],// ["..Q.", "Q...", "...Q", ".Q.."]// ]How it works: We place queens row by row. For each row, we try placing a queen in each column and check if it's safe (doesn't conflict with previously placed queens). If it's safe, we recursively try to place queens in the next row. If we reach a point where we can't place a queen in any column of the current row, we backtrack to the previous row and try a different column.
Example: Permutations
Generate all possible permutations of a given array of distinct integers. This is another classic backtracking problem.
123456789101112131415161718192021222324252627282930313233343536373839function permute(nums) { // Result array to store all permutations const result = []; // Backtracking function function backtrack(current, remaining) { // If there are no more numbers to add, we've found a permutation if (remaining.length === 0) { result.push([...current]); return; } // Try each number in the remaining array for (let i = 0; i < remaining.length; i++) { // Add the current number to our permutation current.push(remaining[i]); // Create a new array without the used number const newRemaining = [...remaining.slice(0, i), ...remaining.slice(i + 1)]; // Recursively generate permutations with the updated arrays backtrack(current, newRemaining); // Backtrack: remove the last added number to try other options current.pop(); } } // Start the backtracking with an empty current array and all numbers in remaining backtrack([], nums); return result;} // Example usage:const nums = [1, 2, 3];const allPermutations = permute(nums);console.log(allPermutations);// Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]How it works: We build permutations one element at a time. For each position, we try each of the remaining numbers. After placing a number, we recursively generate permutations for the remaining positions. After exploring all possibilities with a particular number at a position, we backtrack by removing it and trying the next number.
Time and Space Complexity
Time Complexity
O(b^d), where b is the branching factor (number of choices at each step) and d is the maximum depth of the recursion.
Explanation: In the worst case, we explore all possible combinations. For example, in the permutations problem, the time complexity is O(n!), where n is the number of elements, because there are n! possible permutations.
Space Complexity
O(d), where d is the maximum depth of the recursion.
Explanation: The space complexity is determined by the maximum depth of the recursion stack, which is typically the size of the solution. For example, in the N-Queens problem, the space complexity is O(n), where n is the size of the board.
Optimization Techniques
Pruning
Eliminate branches of the search tree that cannot lead to a valid solution as early as possible. This is the key to making backtracking efficient.
Example: In the N-Queens problem, we check if a queen can be placed in a position before recursively exploring that branch.
State Representation
Choose an efficient representation of the state to minimize the cost of making and undoing choices, and to make validity checks faster.
Example: In the N-Queens problem, we can use a 1D array to represent the board, where the index is the row and the value is the column where a queen is placed.
Ordering Choices
Order the choices so that the most promising ones are tried first, which can lead to finding solutions faster or pruning more branches early.
Example: In constraint satisfaction problems, try the most constrained variables first (those with the fewest valid choices).
Memoization
Store the results of subproblems to avoid redundant computation, especially when the same state can be reached through different paths.
Example: In dynamic programming problems like the Fibonacci sequence, store the results of previously computed values.