Backtracking is recursion with an undo button. We try a choice, explore what happens, and if it doesn’t work out, we undo it and try the next option. It’s the algorithmic equivalent of “let me try this path… nope, dead end, let me go back and try another.”
In simple language, imagine navigating a maze. At each fork, we pick a direction. If we hit a wall, we walk back to the last fork and try a different direction. That’s backtracking.
The Decision Tree
Every backtracking problem can be visualized as a tree. Each node is a decision point, and each branch is a choice we make.
The Universal Backtracking Template
Here’s the beautiful thing — almost every backtracking problem uses the exact same skeleton. Learn this template and we can solve dozens of problems.
function backtrack(result, current, choices, start) {
// 1. Base case: found a valid solution
if (/* goal reached */) {
result.push([...current]); // copy current state
return;
}
// 2. Try each choice
for (let i = start; i < choices.length; i++) {
current.push(choices[i]); // make a choice
backtrack(result, current, choices, i + 1); // explore
current.pop(); // UNDO the choice (backtrack!)
}
}def backtrack(result, current, choices, start):
# 1. Base case: found a valid solution
if True: # goal reached
result.append(current[:]) # copy current state
return
# 2. Try each choice
for i in range(start, len(choices)):
current.append(choices[i]) # make a choice
backtrack(result, current, choices, i + 1) # explore
current.pop() # UNDO the choice (backtrack!)void backtrack(List<List<Integer>> result, List<Integer> current,
int[] choices, int start) {
// 1. Base case: found a valid solution
if (/* goal reached */) {
result.add(new ArrayList<>(current)); // copy current
return;
}
// 2. Try each choice
for (int i = start; i < choices.length; i++) {
current.add(choices[i]); // make a choice
backtrack(result, current, choices, i + 1); // explore
current.remove(current.size() - 1); // UNDO (backtrack!)
}
}The three steps are always: choose, explore, unchoose. The current.pop() (or remove) is the undo — that’s the whole magic of backtracking.
Subsets (Power Set)
Generate all subsets of a given array (LeetCode #78). For each element, we either include it or skip it.
function subsets(nums) {
const result = [];
function backtrack(start, current) {
result.push([...current]); // every path is a valid subset
for (let i = start; i < nums.length; i++) {
current.push(nums[i]); // include nums[i]
backtrack(i + 1, current); // explore with it
current.pop(); // exclude nums[i]
}
}
backtrack(0, []);
return result;
}
// subsets([1,2,3]) => [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]def subsets(nums):
result = []
def backtrack(start, current):
result.append(current[:]) # every path is a valid subset
for i in range(start, len(nums)):
current.append(nums[i]) # include nums[i]
backtrack(i + 1, current) # explore with it
current.pop() # exclude nums[i]
backtrack(0, [])
return result
# subsets([1,2,3]) => [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
static void backtrack(int[] nums, int start,
List<Integer> current, List<List<Integer>> result) {
result.add(new ArrayList<>(current)); // every path is valid
for (int i = start; i < nums.length; i++) {
current.add(nums[i]);
backtrack(nums, i + 1, current, result);
current.remove(current.size() - 1);
}
}Time: O(n * 2^n) — there are 2^n subsets, and we copy each one. Space: O(n) for the recursion stack.
Permutations
Generate all permutations of a given array (LeetCode #46). Unlike subsets, order matters and we use every element.
The key difference from subsets: instead of start, we use a used set to track which elements we’ve already placed.
function permute(nums) {
const result = [];
const used = new Set();
function backtrack(current) {
if (current.length === nums.length) {
result.push([...current]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used.has(i)) continue; // skip already used
used.add(i);
current.push(nums[i]);
backtrack(current);
current.pop(); // undo
used.delete(i); // undo
}
}
backtrack([]);
return result;
}
// permute([1,2,3]) => [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]def permute(nums):
result = []
used = set()
def backtrack(current):
if len(current) == len(nums):
result.append(current[:])
return
for i in range(len(nums)):
if i in used:
continue # skip already used
used.add(i)
current.append(nums[i])
backtrack(current)
current.pop() # undo
used.discard(i) # undo
backtrack([])
return result
# permute([1,2,3]) => [[1,2,3],[1,3,2],[2,1,3],...]static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, used, new ArrayList<>(), result);
return result;
}
static void backtrack(int[] nums, boolean[] used,
List<Integer> current, List<List<Integer>> result) {
if (current.size() == nums.length) {
result.add(new ArrayList<>(current));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
current.add(nums[i]);
backtrack(nums, used, current, result);
current.remove(current.size() - 1); // undo
used[i] = false; // undo
}
}Time: O(n * n!) — there are n! permutations. Space: O(n) for recursion depth.
Combinations
Choose k elements from n elements (LeetCode #77). Like subsets, but we only collect paths of length k.
function combine(n, k) {
const result = [];
function backtrack(start, current) {
if (current.length === k) {
result.push([...current]);
return; // don't go deeper
}
for (let i = start; i <= n; i++) {
current.push(i);
backtrack(i + 1, current);
current.pop();
}
}
backtrack(1, []);
return result;
}
// combine(4, 2) => [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]def combine(n, k):
result = []
def backtrack(start, current):
if len(current) == k:
result.append(current[:])
return # don't go deeper
for i in range(start, n + 1):
current.append(i)
backtrack(i + 1, current)
current.pop()
backtrack(1, [])
return result
# combine(4, 2) => [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]static List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
backtrack(n, k, 1, new ArrayList<>(), result);
return result;
}
static void backtrack(int n, int k, int start,
List<Integer> current, List<List<Integer>> result) {
if (current.size() == k) {
result.add(new ArrayList<>(current));
return;
}
for (int i = start; i <= n; i++) {
current.add(i);
backtrack(n, k, i + 1, current, result);
current.remove(current.size() - 1);
}
}Time: O(k * C(n,k)) — C(n,k) combinations, each copied in O(k).
The Three Flavors Compared
| Problem | Loop starts at | Uses used set? | Base case |
|---|---|---|---|
| Subsets | start (moves forward) | No | Every node is valid |
| Permutations | 0 (always) | Yes | Length == n |
| Combinations | start (moves forward) | No | Length == k |
That’s it. Same template, slightly different parameters. Once we see this, backtracking problems stop being scary.
N-Queens Concept
Place N queens on an N x N chessboard so no two queens attack each other. This is the classic constraint satisfaction problem.
We place queens row by row. For each row, we try each column. Before placing, we check if any existing queen attacks that position (same column, same diagonal). If no conflict, we place it and move to the next row. If we get stuck, we backtrack.
The key optimization is tracking which columns and diagonals are occupied using sets, so our conflict check is O(1) instead of O(n).
Sudoku Solver Concept
Fill in a 9x9 grid so each row, column, and 3x3 box contains digits 1-9. Same idea:
- Find an empty cell
- Try digits 1-9
- If valid (no conflict in row, column, or box), place it and recurse
- If we get stuck, undo and try the next digit
Both N-Queens and Sudoku follow the exact same template — choose, explore, unchoose. The only difference is the constraint checking logic.
When to Use Backtracking
Look for these signals:
- “Find all combinations/permutations/subsets”
- “Generate all valid configurations”
- “Can we place/arrange items following constraints?”
- The problem says “all possible” — that’s almost always backtracking
- Constraint satisfaction (Sudoku, crosswords, N-Queens)
In simple language, if the problem asks us to explore all possibilities and there’s no shortcut to avoid it, backtracking is our tool. We’re systematically trying everything, but we’re smart about it — we prune branches that can’t lead to solutions instead of blindly checking every path.