DSA · Chapter 38 of 40
Backtracking
Backtracking explores all candidate solutions by building them one choice at a time and undoing a choice as soon as it cannot lead to a valid answer. It is DFS over a decision tree.
Permutations, subsets, N-Queens, Sudoku and word search are all backtracking problems. Pruning invalid branches early is what makes it practical.
The template
choose → explore (recurse) → un-choose. Keep a partial solution list and append/pop around the recursive call.
Complexity
Usually exponential: O(2^n) for subsets and O(n!) for permutations, so pruning and constraints matter a lot.
Example 1 (python)
def subsets(nums):
out, path = [], []
def dfs(i):
if i == len(nums):
out.append(path[:])
return
dfs(i + 1) # skip
path.append(nums[i])
dfs(i + 1) # take
path.pop() # undo
dfs(0)
return out
print(subsets([1, 2]))Output
[[], [2], [1], [1, 2]]Each element is either taken or skipped.
Example 2 (python)
def permutations(nums):
out = []
def dfs(path, rest):
if not rest:
out.append(path)
return
for i in range(len(rest)):
dfs(path + [rest[i]], rest[:i] + rest[i + 1:])
dfs([], nums)
return out
print(permutations([1, 2, 3])[:2])Output
[[1, 2, 3], [1, 3, 2]]n! permutations generated by choosing each remaining item.
Key points
- Backtracking is DFS with undo.
- Follow the choose / explore / un-choose template.
- Subsets are O(2^n), permutations O(n!).
- Prune invalid branches as early as possible.
💡 Note: Copy the path (path[:]) when storing it, otherwise later mutations corrupt saved results.