Algorithms
Backtracking (Intro)
Difficulty: Beginner
Listing every subset of a 20-element set produces over a million results, and there is no shortcut: you have to enumerate them. The trick is to do it without writing 20 nested loops. Backtracking solves the entire family of "generate all...
Backtracking (Intro)
Listing every subset of a 20-element set produces over a million results, and there is no shortcut: you have to enumerate them. The trick is to do it without writing 20 nested loops. Backtracking solves the entire family of "generate all configurations" problems with a single recursive template that walks an implicit decision tree.
Backtracking (Intro) introduces that template as the "choose, explore, unchoose" pattern. You will see how each recursive frame picks an option, recurses into the resulting state, and then undoes the choice on the way back up so the next branch starts from a clean slate. Classic problems include generating all subsets and permutations, the N-Queens placement puzzle, and a first look at Sudoku. The lesson also introduces pruning, where invalid partial solutions are cut off early so the algorithm explores far less than the full O(2^n) or O(n!) worst case.
In Recursion Fundamentals, you learned to define a problem in terms of smaller subproblems. Backtracking adds one more idea: state mutated during recursion has to be restored before returning, so siblings in the call tree see the same starting state.
From here, BFS & DFS (Intro) generalizes the same tree-of-states view to actual graphs.
Prerequisites:
Recursion FundamentalsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain the 'choose, explore, unchoose' pattern and how it systematically explores a decision tree.
Implement backtracking to generate all subsets (power set) of a given array.
Implement backtracking to generate all permutations of a given array.
Trace a backtracking decision tree, showing which branches are explored and which are pruned.
Explain the difference between backtracking and brute force, and how pruning improves efficiency.
Analyze the time complexity of backtracking algorithms (O(2^n) for subsets, O(n!) for permutations).
Why This Matters
01
Backtracking solves combinatorial problems (subsets, permutations, combinations) that have no shortcut — you must explore the search space systematically.
02
It is a direct extension of recursion: every backtracking algorithm is recursive, but adds the crucial 'undo' step.
03
Many interview problems require backtracking: generate subsets, permutations, N-Queens, Sudoku, word search, and combination sum.
04
Understanding backtracking builds intuition for dynamic programming — DP optimizes backtracking by caching overlapping subproblems.
Key Terms
7 terms you'll encounter in this lesson
Backtracking
A recursive algorithmic technique that builds solutions incrementally, abandoning partial solutions ('backtracking') as soon as they are determined to be invalid.
Decision tree
A tree where each node represents a choice, and branches represent the consequences of that choice. Backtracking systematically explores this tree.
Choose, explore, unchoose
The three-step pattern of backtracking: (1) make a choice (add an element), (2) explore (recurse), (3) undo the choice (remove the element) to try the next option.
Pruning
Skipping branches of the decision tree early when they cannot lead to valid solutions. Pruning reduces the search space and improves performance.
Power set
The set of all subsets of a given set. For a set of n elements, the power set has 2^n subsets.
Permutation
An arrangement of all elements in a specific order. For n elements, there are n! permutations.
State space
The set of all possible partial and complete solutions that the backtracking algorithm explores.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Backtracking is the same as brute force"
Brute force generates all possible candidates and checks each one. Backtracking builds candidates incrementally and abandons a candidate as soon as it determines it cannot lead to a valid solution (pruning). This often reduces the search space significantly.
"The 'unchoose' step is optional"
The unchoose step is essential. Without it, choices from one branch of the decision tree leak into the next branch, producing incorrect results. The undo restores the state so the next choice starts from the same clean slate.
"Backtracking always has exponential time complexity, so it is useless"
Many combinatorial problems are inherently exponential — there is no polynomial algorithm. Backtracking with good pruning is often the best approach. And even when exponential, backtracking with pruning is much faster than pure brute force.