Pattern 16 of 22
Backtracking Pattern: Template + 105 LeetCode Problems
Build candidates one choice at a time and abandon a branch the moment it cannot work.
- Easy
- 3
- Medium
- 71
- Hard
- 31
What the backtracking pattern is
Backtracking is depth-first search over the tree of partial solutions, with one discipline attached: every choice made on the way down is undone on the way back up, so a single mutable path can stand in for the whole tree instead of copying state at every node. The template is always the same three lines — choose, recurse, un-choose — and the two decisions that make a problem specific are what the recursion index means and where the pruning goes. Pruning is what separates a working answer from a timing out one: rejecting a branch at depth two skips every leaf beneath it, so a check placed before the recursive call is worth far more than the same check at the leaf. The one thing to be deliberate about is the copy: appending the live path to the result list stores a reference that later mutations will corrupt, so the copy has to be taken when the answer is recorded.
When to use it
- The problem asks for all subsets, permutations, combinations, partitions or paths — the arrangements themselves, not a count.
- A valid answer is built incrementally and partial answers can be judged invalid early.
- The constraints are small — n around 20 or less — because the search is exponential by nature.
- You are placing things under conflict rules: queens, sudoku digits, word squares.
The backtracking template in Python
The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 105 problems listed below.
def subsets(nums):
result, path = [], []
def explore(start):
result.append(path[:]) # copy: path keeps mutating after this
for i in range(start, len(nums)):
path.append(nums[i]) # choose
explore(i + 1) # explore what is left
path.pop() # un-choose, restoring the caller's state
explore(0)
return resultComplexity characteristics
- Time
- Exponential — O(n·2ⁿ) for subsets, O(n·n!) for permutations
- Auxiliary space
- O(n), plus the output
The search tree has one leaf per candidate answer, so the running time is the number of answers times the cost of recording each one. There is no polynomial version, which is why the constraints on these problems are small. Pruning does not change the worst case but changes the observed time enormously, because rejecting a branch at depth two removes every leaf beneath it. The working space is the recursion depth and the single mutable path; the result list is output, not working memory.
Eyes only
Meet the backtracking problem you did not practise.
In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.
All 105 backtracking LeetCode problems
Every problem in the library the backtracking pattern applies to, grouped by LeetCode's own difficulty rating. 86 of the 105 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.
Related LeetCode topics
Easy (3)
| No. | Problem | Topics |
|---|---|---|
| 0257 | Binary Tree Paths | |
| 0401 | Binary Watch | |
| 1863 | Sum of All Subset XOR Totals |
Medium (71)
Hard (31)
Backtracking pattern FAQ
What is the backtracking pattern?
Backtracking is depth-first search over the tree of partial solutions, with one discipline attached: every choice made on the way down is undone on the way back up, so a single mutable path can stand in for the whole tree instead of copying state at every node.
How many LeetCode problems use the backtracking pattern?
This page lists 105 LeetCode problems that the backtracking pattern applies to: 3 Easy, 71 Medium and 31 Hard. 86 of them carry a complete Python solution with complexity analysis.
What is the time complexity of the backtracking pattern?
Exponential — O(n·2ⁿ) for subsets, O(n·n!) for permutations time and O(n), plus the output space. The search tree has one leaf per candidate answer, so the running time is the number of answers times the cost of recording each one. There is no polynomial version, which is why the constraints on these problems are small. Pruning does not change the worst case but changes the observed time enormously, because rejecting a branch at depth two removes every leaf beneath it. The working space is the recursion depth and the single mutable path; the result list is output, not working memory.
When should I use the backtracking pattern in an interview?
The problem asks for all subsets, permutations, combinations, partitions or paths — the arrangements themselves, not a count. A valid answer is built incrementally and partial answers can be judged invalid early.
Which backtracking problem should I start with?
LeetCode 257. Binary Tree Paths is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.
What patterns are related to backtracking?
Depth-First Search, Dynamic Programming, Bit Manipulation, Trie. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.
More ways in: all 22 patterns, the curated study lists, or the full problem list.