Overview
Backtracking explores a tree of decisions. At each step you make a choice, recurse to make the rest, and then undo the choice so the next option starts from a clean state. Subsets, permutations, combinations, N-Queens and Sudoku are all walks through such a tree.
The output of these problems is often exponential in size, so the goal is not a polynomial algorithm but an efficient search: generate each candidate exactly once, avoid duplicates, and prune branches early when they cannot possibly succeed. Good pruning is the difference between an instant answer and a timeout.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| All subsets | O(n · 2ⁿ) |
| All permutations | O(n · n!) |
| Combinations of size k | O(k · C(n, k)) |
Patterns to recognise
Subsets / combinations
Use it for: Subsets, combination sum, letter combinations.
Loop i from start; recurse with i + 1 (or i if reuse is allowed).
Permutations
Use it for: Permutations, next arrangement, anagram generation.
Loop over all items; skip those already used in the path.
Grid search
Use it for: Word search, N-Queens, Sudoku.
Mark a cell or position as used before recursing and unmark it afterwards.
Code template
def combination_sum(candidates, target):
candidates.sort()
result, path = [], []
def backtrack(start, remaining):
if remaining == 0:
result.append(path[:]) # copy the current path
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # sorted, so the rest are too big
path.append(candidates[i]) # choose
backtrack(i, remaining - candidates[i]) # i: reuse allowed
path.pop() # un-choose
backtrack(0, target)
return result
class CombinationSum {
vector<vector<int>> result;
vector<int> path;
void backtrack(const vector<int>& c, int start, int remaining) {
if (remaining == 0) { result.push_back(path); return; }
for (int i = start; i < (int)c.size(); ++i) {
if (c[i] > remaining) break; // sorted, so the rest are too big
path.push_back(c[i]); // choose
backtrack(c, i, remaining - c[i]);
path.pop_back(); // un-choose
}
}
public:
vector<vector<int>> solve(vector<int> candidates, int target) {
sort(candidates.begin(), candidates.end());
backtrack(candidates, 0, target);
return result;
}
};
Common mistakes
- Appending the path itself instead of a copy — every saved answer then changes as the path does.
- Forgetting to undo a choice (pop, unmark) corrupts sibling branches.
- Skipping duplicates across levels instead of within one level drops valid answers.
Quick check
Three questions on Backtracking. Get all three right to earn +15 XP.
-
What is the core loop of backtracking?
Undoing restores the state so the next option starts clean.
-
How many subsets does a set of n distinct elements have?
Each element is independently in or out.
-
What is pruning in backtracking?
Cutting dead branches early is what makes exponential searches practical.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Binary WatchLeetCode Easy +20
- SubsetsLeetCode Medium +40
- PermutationsLeetCode Medium +40
- Combination SumLeetCode Medium +40
- Subsets IILeetCode Medium +40
- Letter Combinations of a Phone NumberLeetCode Medium +40
- Word SearchLeetCode Medium +40
- Palindrome PartitioningLeetCode Medium +40
- N-QueensLeetCode Hard +70
- Sudoku SolverLeetCode Hard +70
Stuck on Backtracking?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor