Why We Need Backtracking & How to Think About It
Imagine you are standing at the entrance of a dark maze holding a spool of thread. To find the exit, you walk down a corridor. Every time you hit a junction, you make a choice and keep walking. If you hit a dead end, you rewind your thread, walk back to the last junction, and try the next available path. You don't teleport or clone yourself; you are a single explorer who systematically visits every path by remembering to undo your steps.
This is Backtracking. It is a systematic way to search through all possible configurations (e.g., subsets, permutations, board states).
The core algorithm is a three-step cycle:
- Choose: Make a decision (e.g., place a queen, add a number to a subset).
- Explore: Recurse to make subsequent choices with the current choice active.
- Un-choose: Undo your decision (e.g., remove the queen, pop the number). This is the key: it cleans up the state so the next sibling branch starts with a clean slate, letting you reuse the same memory (like a single path list) instead of making expensive copies.
Watch it run: N-Queens
The classic constraint puzzle: place queens so none can attack another. Watch three things — choices being made (green), illegal squares being rejected before going deeper (red ✕), and the backtrack itself: a queen being lifted off the board when everything below it failed.
1/32Place 4 queens on a 4×4 board so none can attack another (no shared row, column or diagonal). Brute force would test every arrangement; backtracking abandons bad ones early. One queen per row — row by row.
Watch it run: subsets
Most backtracking interview problems are secretly this: walk the items left to right, and for each one make a yes/no decision. Every route through the decisions produces one subset.
1/24List every subset of {1, 2, 3}. Walk the numbers left to right; for each one make a yes/no decision: take it, or leave it. 3 decisions → 2^3 = 8 subsets.
The template
Build a candidate incrementally; at each step choose an option, explore deeper, then un-choose (undo) to try the next. It's DFS over the space of partial solutions — the "graph" is imaginary: nodes are partial answers, edges are choices.
# Subsets template (Include/Skip)
# Python
def subsets(nums):
res, path = [], []
def backtrack(start):
res.append(path[:]) # every node is a valid subset
for i in range(start, len(nums)):
path.append(nums[i]) # choose
backtrack(i + 1) # explore (i+1 ⇒ no reuse, no dupes)
path.pop() # un-choose
backtrack(0)
return res
// Java
import java.util.ArrayList;
import java.util.List;
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
backtrack(nums, 0, path, res);
return res;
}
private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
res.add(new ArrayList<>(path)); // record a copy of current subset
for (int i = start; i < nums.length; i++) {
path.add(nums[i]); // choose
backtrack(nums, i + 1, path, res); // explore
path.remove(path.size() - 1); // un-choose (backtrack)
}
}
// C++
#include <vector>
void backtrack(const std::vector<int>& nums, int start, std::vector<int>& path, std::vector<std::vector<int>>& res) {
res.push_back(path); // record a copy of current subset
for (int i = start; i < nums.size(); i++) {
path.push_back(nums[i]); // choose
backtrack(nums, i + 1, path, res); // explore
path.pop_back(); // un-choose (backtrack)
}
}
std::vector<std::vector<int>> subsets(const std::vector<int>& nums) {
std::vector<std::vector<int>> res;
std::vector<int> path;
backtrack(nums, 0, path, res);
return res;
}
The start index is what prevents duplicate subsets; for permutations you'd
instead track a used[] set and iterate all indices.
Knowing the shape
| Problem | Branch on | Avoid dupes via |
|---|---|---|
| Subsets | include/skip each item | start index |
| Combinations (k of n) | pick next ≥ start | start index |
| Permutations | any unused item | used[] flags |
| Partition / N-Queens / Sudoku | each valid placement | constraint check |
How to recognize a backtracking problem
The wording gives it away. Reach for backtracking when the problem says:
- "all subsets / all permutations / all combinations / every way to…" → you're asked to enumerate, not to find one best answer.
- "place / arrange / assign … such that no two conflict" → constraint puzzle (N-Queens, Sudoku, graph coloring).
- "can you split / partition the input into groups that…" → try assignments, undo on failure.
- The input is tiny (n ≤ ~15). Exponential is expected; the question is whether your recursion is clean and your pruning is real.
If instead it asks for the count of ways or the best value — and the same sub-questions repeat — that's dynamic programming: DP remembers answers, backtracking enumerates paths.
Pruning is the whole point
Naive enumeration is O(2ⁿ) or O(n!). Pruning — cutting branches that can't lead to a valid/better solution — is what makes it pass. You saw it in the N-Queens player: the red ✕ squares were rejected before recursing, killing whole subtrees of doomed arrangements in one comparison. Sort to enable early termination, skip equal siblings to dedupe, and check constraints before recursing.
If the constraints say n ≤ ~12–15, exponential backtracking is expected — the interviewer wants a clean recursion with correct pruning, not a polynomial trick. The input size is the hint (see the DSA study plan).
Think one through
PROBLEMGiven an array of distinct numbers like [1, 2, 3], return every possible ordering: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].
- 1
Spot the pattern
“What word in the problem tells me which tool to grab?”
- 2
Frame the decisions
“Building one permutation step by step — what is the choice at each step?”
unlocks after the stage above - 3
Write the skeleton
“Where exactly do choose, explore, and un-choose go?”
unlocks after the stage above - 4
Check the cost, test the edges
“How much work is this, and what inputs could break it?”
unlocks after the stage above
// Java — Permutations
import java.util.ArrayList;
import java.util.List;
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, path, used, res);
return res;
}
private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> res) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path)); // full -> record copy
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
path.add(nums[i]); used[i] = true; // choose
backtrack(nums, path, used, res); // explore
path.remove(path.size() - 1); used[i] = false; // un-choose
}
}
// C++ — Permutations
#include <vector>
void backtrack(const std::vector<int>& nums, std::vector<int>& path, std::vector<bool>& used, std::vector<std::vector<int>>& res) {
if (path.size() == nums.size()) {
res.push_back(path); // record copy
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i]) continue;
path.push_back(nums[i]); used[i] = true; // choose
backtrack(nums, path, used, res); // explore
path.pop_back(); used[i] = false; // un-choose
}
}
std::vector<std::vector<int>> permute(const std::vector<int>& nums) {
std::vector<std::vector<int>> res;
std::vector<int> path;
std::vector<bool> used(nums.size(), false);
backtrack(nums, path, used, res);
return res;
}
1. In choose → explore → un-choose, what breaks if you forget the un-choose step?
2. A problem says: 'count the number of ways to climb n stairs taking 1 or 2 steps'. Backtracking or DP?
3. Why does checking N-Queens conflicts BEFORE recursing matter so much?
Practice — climb the ladder
Every backtracking solution is the same skeleton: choose → explore → un-choose. The only things that change are the choice list and the pruning.
Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.
Warm-up
enumerate without pruning- SubsetsMedium
Include/exclude branching — the decision tree in its purest form.
Cartesian-product recursion — one digit per level, combine on the way down.
Core
dedup, reuse, and board walks- PermutationsMedium
Used-set bookkeeping — order matters now; un-choose restores state EXACTLY.
- Combination SumMedium
Reuse allowed + start-index discipline to avoid duplicate combinations.
- Generate ParenthesesMedium
Pruning by invariant — never place a close past its open count.
- Word SearchMedium
Grid backtracking — mark the cell, explore 4 ways, UNMARK; the un-choose drill.
- Palindrome PartitioningMedium
Partition-point recursion — cut positions as choices, validity as pruning.
Stretch
constraint propagation at full power- N-QueensHard
Column/diagonal sets as O(1) constraint checks — pruning as the main event.
- Sudoku SolverHard
The full search-with-constraints experience — choose the cell, try 9, backtrack.