Backtracking Template
Backtracking = DFS + undo. The universal template: choose (add to path), recurse (explore), unchoose (remove from path). Always ask: what are the choices at each step? What is the base case? What constraint prunes the search? Pruning is what separates backtracking from brute-force: eliminate branches early when a partial solution cannot possibly lead to a valid complete solution. Time complexity without pruning: O(k^n) where k=choices, n=depth. Good pruning can reduce this dramatically in practice.
def backtrack(path, choices):
if is_complete(path):
result.append(path[:]) # copy, not reference
return
for choice in choices:
if is_valid(path, choice): # PRUNE invalid choices
path.append(choice) # CHOOSE
backtrack(path, next_choices(path, choice)) # RECURSE
path.pop() # UNCHOOSE (undo)Subsets with and without Duplicates
# Subsets (LC 78): no duplicates in input
def subsets(nums: list[int]) -> list[list[int]]:
result = []
def bt(start, path):
result.append(path[:]) # add at every node, not just leaves
for i in range(start, len(nums)):
path.append(nums[i])
bt(i + 1, path)
path.pop()
bt(0, [])
return result
# Subsets II (LC 90): input has duplicates
def subsets_with_dup(nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
def bt(start, path):
result.append(path[:])
for i in range(start, len(nums)):
# Skip duplicates at the same level
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
bt(i + 1, path)
path.pop()
bt(0, [])
return resultPermutations with and without Duplicates
# Permutations (LC 46): no duplicates
def permute(nums: list[int]) -> list[list[int]]:
result = []
def bt(path, used):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]: continue
used[i] = True
path.append(nums[i])
bt(path, used)
path.pop()
used[i] = False
bt([], [False] * len(nums))
return result
# Permutations II (LC 47): input has duplicates
def permute_unique(nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
def bt(path, used):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]: continue
# Skip duplicate: same value as previous AND previous not used
# (if previous was used, we are in a different branch - allow)
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
path.append(nums[i])
bt(path, used)
path.pop()
used[i] = False
bt([], [False] * len(nums))
return resultCombination Sum
# Combination Sum (LC 39): reuse elements, find all combos summing to target
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
result = []
candidates.sort()
def bt(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # sorted: no point continuing
path.append(candidates[i])
bt(i, path, remaining - candidates[i]) # i (not i+1): reuse allowed
path.pop()
bt(0, [], target)
return result
# Combination Sum II (LC 40): each element used at most once, has duplicates
def combination_sum2(candidates, target):
candidates.sort()
result = []
def bt(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining: break
if i > start and candidates[i] == candidates[i-1]: continue # skip dup
path.append(candidates[i])
bt(i + 1, path, remaining - candidates[i])
path.pop()
bt(0, [], target)
return resultN-Queens
def solve_n_queens(n: int) -> list[list[str]]:
result = []
cols = set()
diag1 = set() # row - col (top-left to bottom-right diagonal)
diag2 = set() # row + col (top-right to bottom-left diagonal)
def bt(row, board):
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 # attacked
cols.add(col); diag1.add(row-col); diag2.add(row+col)
board[row][col] = 'Q'
bt(row + 1, board)
board[row][col] = '.'; cols.remove(col)
diag1.remove(row-col); diag2.remove(row+col)
board = [['.'] * n for _ in range(n)]
bt(0, board)
return result
# Key insight: use sets for O(1) attack checking instead of O(n) scan
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the universal backtracking template?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The backtracking template has three steps: (1) Choose: add an option to the current path. (2) Recurse: explore all further possibilities from this state. (3) Unchoose: remove the option from the path (undo the choice). Always copy the path when adding to results (result.append(path[:])) – never store a reference. The base case returns when the path is complete. Pruning (skipping invalid choices before recursing) is what makes backtracking efficient – without pruning, it is brute-force exponential search.”}},{“@type”:”Question”,”name”:”How do you handle duplicates in subset and permutation backtracking problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sort the input first. In the loop, skip an element if it equals the previous element AND the previous element has not been used in the current recursion level. For subsets with duplicates (LC 90): if i > start and nums[i] == nums[i-1], continue. For permutations with duplicates (LC 47): if i > 0 and nums[i] == nums[i-1] and not used[i-1], continue. The "not used[i-1]" condition is key: if the previous duplicate was used, we are in a different branch and should allow the current element; only skip when the previous duplicate was not used (same horizontal level).”}},{“@type”:”Question”,”name”:”What is the difference between LC 39 and LC 40 (Combination Sum)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”LC 39: elements can be reused unlimited times. In the recursion, pass i (not i+1) as the start index to allow reusing the current element. LC 40: each element used at most once, but input has duplicates. Pass i+1, and skip duplicates at the same level (if i > start and candidates[i] == candidates[i-1]: continue). Both benefit from sorting: since the array is sorted, if candidates[i] > remaining, break early (all further elements are also too large). This pruning significantly reduces the search space.”}},{“@type”:”Question”,”name”:”How do you solve N-Queens efficiently in backtracking?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Place one queen per row (row index = recursion depth). Track three sets: cols (occupied columns), diag1 (occupied row-col diagonals), diag2 (occupied row+col diagonals). For each column in the current row, check if (col in cols) or ((row-col) in diag1) or ((row+col) in diag2) – if any, skip. This O(1) attack check avoids scanning the entire board. Add to all three sets before recursing, remove from all three when backtracking. Total time: O(n!) but heavily pruned in practice. This is LC 51/52.”}},{“@type”:”Question”,”name”:”When should you use backtracking vs dynamic programming?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use backtracking when: you need all solutions (not just count or optimal), the problem has constraints that prune the search space, or you need to enumerate combinations/permutations/subsets. Use DP when: you only need the count of solutions or the optimal value, the problem has overlapping subproblems, and you do not need to reconstruct all solutions. Example: "find all valid parenthesis strings" – backtracking. "Count valid parenthesis strings of length 2n" – DP (Catalan number). "Find all combination sums" – backtracking. "Does a combination sum exist?" – DP (subset sum).”}}]}
Meta coding interviews test backtracking extensively. See common patterns for Meta interview: backtracking and combinatorics problems.
Atlassian coding rounds include backtracking problems. Review patterns for Atlassian interview: backtracking and search problems.
Apple coding interviews test backtracking and N-Queens style problems. See patterns for Apple interview: backtracking and constraint satisfaction.