Backtracking is systematic trial and error — explore a decision tree, and when you reach a dead end, undo the last choice and try another. It is the go-to technique for constraint satisfaction and combinatorial search problems that cannot be solved greedily or with dynamic programming. Mastering the backtracking template and its variants covers 15+ LeetCode problems.
The Universal Backtracking Template
def backtrack(state, choices):
if is_complete(state):
result.append(state[:]) # copy current solution
return
for choice in choices:
if is_valid(state, choice):
state.append(choice) # make choice
backtrack(state, next_choices) # explore
state.pop() # undo choiceEvery backtracking problem maps to this template. The key variables: what constitutes a complete state, what choices are available at each step, and what makes a choice invalid. Pruning (the is_valid check) is what separates an efficient solution from brute force.
Pattern 1: Permutations
Generate all orderings of n elements. Each element appears exactly once. Track which elements are used with a boolean array or by swapping elements in place.
def permutations(nums):
result = []
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:])
return
for i, num in enumerate(nums):
if used[i]:
continue
used[i] = True
path.append(num)
backtrack(path, used)
path.pop()
used[i] = False
backtrack([], [False] * len(nums))
return resultTime: O(n * n!). Permutations II (with duplicates): sort first, then skip if nums[i] == nums[i-1] and not used[i-1].
Pattern 2: Combinations
Choose k elements from n, where order does not matter. Pass a start index to avoid revisiting earlier elements.
def combinations(n, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(path[:])
return
# Pruning: need at least k - len(path) more elements
for i in range(start, n + 1 - (k - len(path)) + 1):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return resultThe pruning bound (n + 1 – remaining) prevents exploring branches that cannot produce k elements. Without it, the loop runs to n regardless. Combination Sum (elements can repeat): pass i instead of i+1 as the next start index.
Pattern 3: Subsets (Power Set)
Generate all 2^n subsets. Two approaches: (1) at each index, decide include or exclude; (2) at each index, extend all previously generated subsets.
def subsets(nums):
result = [[]]
def backtrack(start, path):
for i in range(start, len(nums)):
path.append(nums[i])
result.append(path[:]) # every partial path is a valid subset
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return resultUnlike permutations and combinations, we add to result at every node of the tree, not just leaves. Subsets II (with duplicates): sort first, skip if i > start and nums[i] == nums[i-1].
Pattern 4: N-Queens
Place n queens on an n×n board so no two queens share a row, column, or diagonal. Place one queen per row; prune using column and diagonal sets.
def solveNQueens(n):
result = []
cols, diag1, diag2 = set(), set(), set()
board = [['.']] * n for _ in range(n)]
def backtrack(row):
if row == n:
result.append(["".join(r) for r in board])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
cols.add(col); diag1.add(row - col); diag2.add(row + col)
board[row][col] = 'Q'
backtrack(row + 1)
board[row][col] = '.'
cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)
backtrack(0)
return resultThe diagonal invariants: cells on the same left diagonal share the same (row – col) value; cells on the same right diagonal share the same (row + col) value. Using sets gives O(1) conflict checks.
Pattern 5: Word Search on a Grid
Find if a word exists in a 2D grid following adjacent cells. Mark cells as visited during recursion, unmark on backtrack.
def exist(board, word):
rows, cols = len(board), len(board[0])
def backtrack(r, c, idx):
if idx == len(word):
return True
if r = rows or c = cols:
return False
if board[r][c] != word[idx]:
return False
temp = board[r][c]
board[r][c] = '#' # mark visited
found = any(backtrack(r+dr, c+dc, idx+1)
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)])
board[r][c] = temp # unmark
return found
return any(backtrack(r, c, 0)
for r in range(rows) for c in range(cols))
Pattern 6: Expression / Phone Letter Combinations
Generate all strings from digit-to-letter mappings (LeetCode 17). The choices at each level are the letters corresponding to the current digit. Classic “generate all strings” pattern.
def letterCombinations(digits):
if not digits:
return []
mapping = {"2":"abc","3":"def","4":"ghi","5":"jkl",
"6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
result = []
def backtrack(idx, path):
if idx == len(digits):
result.append("".join(path))
return
for char in mapping[digits[idx]]:
path.append(char)
backtrack(idx + 1, path)
path.pop()
backtrack(0, [])
return resultPruning Strategies
Pruning is what makes backtracking efficient. Common techniques:
- Constraint propagation: Before recursing, propagate constraints to reduce the search space (Sudoku MRV heuristic — pick the cell with fewest valid values)
- Feasibility check: If remaining candidates cannot satisfy the constraint, cut early (Combination Sum — if remaining target becomes negative, stop)
- Symmetry breaking: Skip duplicates in the candidate list (sort + skip equal neighbors)
- Forward checking: After placing a queen, immediately check if any remaining row has no valid column
Complexity
Backtracking worst-case time is exponential — O(n!), O(2^n), or O(k^n) depending on the branching factor. In practice, pruning reduces this dramatically. Recognize the pattern by: the problem asks for ALL solutions (not just one optimal), decisions are reversible, and the solution space can be represented as a tree.
Frequently Asked Questions
When should you use backtracking instead of dynamic programming?
Use backtracking when you need ALL solutions (not just the optimal one), when decisions are reversible, and when the solution space is a tree of discrete choices. Classic signals: "generate all permutations," "find all valid combinations," "return all paths." Use dynamic programming when the problem has overlapping subproblems and optimal substructure — you need ONE optimal answer, and the same subproblem is solved multiple times. For example, "find the minimum path cost" is DP; "find all minimum-cost paths" might combine DP and backtracking. The tell: if the problem says "return all," think backtracking. If it says "return the minimum/maximum count/value," think DP or greedy first.
How does the start index parameter work in combination problems?
The start index prevents reusing earlier elements and ensures combinations (not permutations) are generated. In a combination problem with candidates [1,2,3] and target k=2, starting from index 0 would generate [1,2], [1,3], and [2,3] — each pair counted once. Without the start index, you would also generate [2,1] and [3,1] and [3,2], which are duplicates. The pattern: when order does not matter (subsets, combinations), pass start=i+1 to avoid revisiting earlier elements. When elements can be reused (Combination Sum), pass start=i instead of i+1. When order matters (permutations), use a visited boolean array instead of a start index — any unvisited element can be chosen at each position.
How do you handle duplicate elements in permutations and subsets?
Sort the input first, then skip duplicate elements at the same recursion level. The rule: if nums[i] == nums[i-1] and nums[i-1] has NOT been used in the current path, skip nums[i]. The "not used" condition is key — it means we are at the same recursion level (considering the same position), not that the element never appears in the solution. For permutations with duplicates (LeetCode 47): if used[i] is False and nums[i] == nums[i-1] and not used[i-1], skip. For subsets with duplicates (LeetCode 90): if i > start and nums[i] == nums[i-1], skip. Sorting ensures duplicates are adjacent, making the comparison O(1).
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “When should you use backtracking instead of dynamic programming?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Use backtracking when you need ALL solutions (not just the optimal one), when decisions are reversible, and when the solution space is a tree of discrete choices. Classic signals: “generate all permutations,” “find all valid combinations,” “return all paths.” Use dynamic programming when the problem has overlapping subproblems and optimal substructure — you need ONE optimal answer, and the same subproblem is solved multiple times. For example, “find the minimum path cost” is DP; “find all minimum-cost paths” might combine DP and backtracking. The tell: if the problem says “return all,” think backtracking. If it says “return the minimum/maximum count/value,” think DP or greedy first.”
}
},
{
“@type”: “Question”,
“name”: “How does the start index parameter work in combination problems?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The start index prevents reusing earlier elements and ensures combinations (not permutations) are generated. In a combination problem with candidates [1,2,3] and target k=2, starting from index 0 would generate [1,2], [1,3], and [2,3] — each pair counted once. Without the start index, you would also generate [2,1] and [3,1] and [3,2], which are duplicates. The pattern: when order does not matter (subsets, combinations), pass start=i+1 to avoid revisiting earlier elements. When elements can be reused (Combination Sum), pass start=i instead of i+1. When order matters (permutations), use a visited boolean array instead of a start index — any unvisited element can be chosen at each position.”
}
},
{
“@type”: “Question”,
“name”: “How do you handle duplicate elements in permutations and subsets?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Sort the input first, then skip duplicate elements at the same recursion level. The rule: if nums[i] == nums[i-1] and nums[i-1] has NOT been used in the current path, skip nums[i]. The “not used” condition is key — it means we are at the same recursion level (considering the same position), not that the element never appears in the solution. For permutations with duplicates (LeetCode 47): if used[i] is False and nums[i] == nums[i-1] and not used[i-1], skip. For subsets with duplicates (LeetCode 90): if i > start and nums[i] == nums[i-1], skip. Sorting ensures duplicates are adjacent, making the comparison O(1).”
}
}
]
}