Backtracking
1 / 11
Recursion with choice and undo
DFS on an implicit decision tree
def backtrack(path, choices):
if is_complete(path):
result.append(path[:]) # Copy!
return
for choice in choices:
if not is_valid(choice):
continue # Prune
path.append(choice) # Choose
backtrack(path, ...) # Explore
path.pop() # Unchoose
Include or exclude each element
def backtrack(start, path):
result.append(path[:]) # Every path is valid
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path) # i+1 avoids duplicates
path.pop()
2^n subsets total
Use any unused element
def backtrack(path):
if len(path) == n:
result.append(path[:])
return
for i in range(n):
if used[i]:
continue
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
n! permutations total
Track attacked positions:
cols[col] — column occupieddiag1[row-col] — main diagonaldiag2[row+col] — anti-diagonalif cols[col] or diag1[d1] or diag2[d2]:
continue # Prune
| Subsets | Permutations |
|---|---|
| Order doesn't matter | Order matters |
| Any size (0 to n) | Fixed size (n) |
Use start index |
Use used array |
| 2^n results | n! results |
Wrong:
result.append(path) # References same list
Correct:
result.append(path[:]) # Creates copy
| Problem | Solutions | Time |
|---|---|---|
| Subsets | 2^n | O(n * 2^n) |
| Permutations | n! | O(n * n!) |
| N-Queens | varies | O(n!) |