Backtracking
Overview
Backtracking is an advanced algorithmic technique used for generating all possible solutions (or finding one specific optimal solution) to complex combinatorics problems, such as solving a Sudoku puzzle, the N-Queens problem, or finding all valid permutations of a string.
It is an evolution of standard recursion. In Backtracking, you incrementally build candidates to the solutions. The moment you determine a candidate cannot possibly be completed to a valid solution, you 'backtrack' (undo your last step) and try a different path. This is fundamentally different from a naive Brute Force approach, which generates every single complete possibility before checking if they are valid.
Think of backtracking like navigating a maze. You walk down a path, making choices at intersections. If you hit a dead end, you physically walk backwards (backtrack) to the last intersection and try a different route. By discarding entirely invalid branches of logic early (a concept known as 'Pruning'), backtracking avoids billions of useless computations, making exponentially hard problems solvable.
Syntax
import java.util.ArrayList;
import java.util.List;
public class Backtracking {
// Problem: Generate all possible orderings (permutations) of an array
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
backtrack(results, new ArrayList<>(), nums);
return results;
}
private static void backtrack(List<List<Integer>> results, List<Integer> currentList, int[] nums) {
// 1. Base Case: If the current list is full, we found a valid solution!
if (currentList.size() == nums.length) {
results.add(new ArrayList<>(currentList)); // Add a COPY of the list
return;
}
// 2. Iterate through all possible choices at this step
for (int i = 0; i < nums.length; i++) {
// Pruning: Skip numbers we've already used in this permutation
if (currentList.contains(nums[i])) continue;
// A. CHOOSE
currentList.add(nums[i]);
// B. EXPLORE (Recursive call down this path)
backtrack(results, currentList, nums);
// C. UNCHOOSE (Backtrack!)
// Remove the last item we added to try the next possible number
currentList.remove(currentList.size() - 1);
}
}
}Common Pitfalls
- Failing to make a deep copy of the solution list in the base case. Java passes objects by reference. If you write
results.add(currentList), you are adding a reference to the active list. Later, when the algorithm backtracks and clears the list, your stored solution will also become completely empty! You must always donew ArrayList<>(currentList). - Forgetting the 'Unchoose' step. The core of backtracking is reverting the state. If you add an item to
currentListbut don'tremove()it after the recursive call returns, your list will just grow infinitely, contaminating all future branches. - Poor pruning logic. Backtracking algorithms naturally have factorial O(N!) or exponential O(2^N) time complexities. If you do not actively
continueorreturnwhen a path is proven invalid early on, your solution will Time Out on competitive programming platforms.
Interview Questions
1. Choose: Make a choice and modify the state (e.g., add an item to a list or place a Queen on a board). 2. Explore: Recursively call the function to explore all paths branching from this specific choice. 3. Unchoose: Revert the choice you made in step 1 (remove the item) to reset the state cleanly for the next iteration of the loop.
Backtracking is a highly specific, optimized form of DFS. Pure DFS traverses every single node in a tree blindly. Backtracking actively evaluates the current state, and if it violates problem constraints, it 'prunes' the branch, stopping the DFS instantly and retreating up the tree.
Real-World Example
Route Optimization and Logistics. If a delivery driver has 10 packages, an algorithm must find the shortest possible route connecting all 10 houses (a variation of the Traveling Salesperson Problem). Backtracking generates routes: House A -> House B -> House C. If the distance suddenly exceeds a known 'best route', the algorithm backtracks immediately, ignoring the millions of possible routes that branch off that terrible start.
import java.util.*;
public class RouteOptimizer {
int shortestDistance = Integer.MAX_VALUE;
List<String> bestRoute = new ArrayList<>();
public void findBestRoute(List<String> currentRoute, int currentDistance, List<String> unvisited) {
// Base Case: All stops visited
if (unvisited.isEmpty()) {
if (currentDistance < shortestDistance) {
shortestDistance = currentDistance;
bestRoute = new ArrayList<>(currentRoute);
}
return;
}
for (int i = 0; i < unvisited.size(); i++) {
String nextStop = unvisited.get(i);
int distanceToNext = calculateDistance(currentRoute.get(currentRoute.size() - 1), nextStop);
// PRUNING: If this path is already longer than our best, stop exploring it entirely!
if (currentDistance + distanceToNext >= shortestDistance) continue;
// Choose
currentRoute.add(nextStop);
unvisited.remove(i);
// Explore
findBestRoute(currentRoute, currentDistance + distanceToNext, unvisited);
// Unchoose (Backtrack)
unvisited.add(i, nextStop);
currentRoute.remove(currentRoute.size() - 1);
}
}
private int calculateDistance(String a, String b) { return 10; /* Mock logic */ }
}Check Your Knowledge
Test your understanding of Backtracking with these quick questions.