Backtracking is used when you need to exhaustively process all possible combinations for a given problem. This is realized by traversing through the entire decision tree (remember that traversal algorithms visit every connected node, so we traverse the entire problem space), or by processing each position on the grid/matrix.
I especially like Competitive Programmer’s Handbook for this topic, it gives you a good framework to grasp the core idea. I also highly recommend solving almost all backtracking questions in Neetcode 150. Especially watch the solutions if you need to understand what is meant by decision trees.
Backtracking problems are for exhaustive searches. So, unlike greedy or DP problems, you will have combinatorial complexity, such as $O(2^n)$; and your constraints will also reflect that. You may often see that $n < 20$, which is a hint that this problem is not solvable in polynomial time, and backtracking might be used as a technique.
Here are the 4 solutions I took note of since I think they cover almost all questions type within backtracking.
Making Subsets 🔗
def search(k):
if k == n:
# Process subset
else:
subset.append(k)
search(k+1)
subset.pop()
search(k+1)
- Time Complexity: O(n * 2^n)
- Space Complexity (Auxiliary): O(n) for the subset
Permutations 🔗
# dfs(subset, chosen): appends all permutations to given subset using
# elements not in chosen
def permute(self, nums: List[int]) -> List[List[int]]:
ans = []
chosen = [False for _ in range(len(nums))]
def dfs(subset, chosen):
if len(subset) == len(nums):
ans.append(subset.copy())
else:
for i in range(len(nums)):
if not chosen[i]:
chosen[i] = True
subset.append(nums[i])
dfs(subset, chosen)
subset.pop()
chosen[i] = False
dfs([], chosen)
return ans
- Time Complexity: O(n * n!)
- Space Complexity (Auxiliary): O(n) for the permutation
N-Queens 🔗
# search(row_idx, solution): returns all solutions searching for given row_idx and solution
# def solveNQueens(self, n: int) -> List[List[str]]:
ans = []
columns = [False for _ in range(n)],
diag1, diag2 = [False for _ in range(2*n - 1)], [False for _ in range(2*n - 1)]
def search(row_idx: int, solution: List[List[str]]):
if row_idx == n:
ans.append(solution.copy())
return
for j in range(n):
if columns[j] or diag1[row_idx + j] or diag2[j - row_idx + n - 1]:
continue
columns[j] = diag1[row_idx + j] = diag2[j - row_idx + n - 1] = True
solution.append(''.join(['Q' if i==j else '.' for i in range(n)]))
search(row_idx + 1, solution)
solution.pop()
columns[j] = diag1[row_idx + j] = diag2[j - row_idx + n - 1] = False
search(0, [])
return ans
- Time Complexity: O(n * n!)
- Space Complexity (Auxiliary): O(n) for columns, diag1, diag2
Word Search 🔗
# Search starting on word[k:n] from pos, with path already visited
def dfs(k: int, r: int, c: int, path: Set):
# Successful search, process item
if k == len(word):
return True
else:
# Current pos is INVALID. Backtrack.
if (not 0 <= r < len(board) or
not 0 <= c < len(board[0]) or
board[r][c] != word[k] or
(r, c) in path
):
return False
# Current is VALID. Add to path and continue search
path.add((r,c))
res = (dfs(k + 1, r + 1, c, path) or
dfs(k + 1, r - 1, c, path) or
dfs(k + 1, r, c + 1, path) or
dfs(k + 1, r, c - 1, path))
path.discard((r,c))
return res
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(0, i, j, set()):
return True
return False