Backtracking
DSA · Algorithm Techniques
Theory
Backtracking builds candidate solutions one choice at a time and abandons ("backtracks" from) a partial candidate as soon as it cannot lead to a valid solution. The template is choose, explore, un-choose. It explores a search tree of possibilities, so the worst case is exponential, but pruning invalid branches early makes it practical for puzzles and combinatorial problems.
Why we use it
It systematically finds all solutions (or one valid solution) to constraint problems without writing complex special cases.
When to use it
Use it for permutations, combinations, subsets, N-Queens, Sudoku, word search, and generating valid parentheses.
How it works
- choose(state)
- State is a complete solution? Yes: Record it. No: For each option.
- Option is valid? Yes: Apply it, recurse, then undo it. No: Try next option.
- Explored all options
Syntax
def backtrack(path, choices):
if complete(path): record(path); return
for c in choices:
if valid(c):
path.append(c) # choose
backtrack(path, ...) # explore
path.pop() # un-chooseExample
def subsets(items):
result = []
def bt(i, path):
if i == len(items):
result.append(list(path)); return
bt(i + 1, path)
path.append(items[i]); bt(i + 1, path); path.pop()
bt(0, [])
return result
def solve_queens(n):
solutions = []
cols, d1, d2 = set(), set(), set()
board = []
def place(r):
if r == n:
solutions.append(list(board)); return
for c in range(n):
if c in cols or r - c in d1 or r + c in d2:
continue
cols.add(c); d1.add(r - c); d2.add(r + c); board.append(c)
place(r + 1)
cols.remove(c); d1.remove(r - c); d2.remove(r + c); board.pop()
place(0)
return solutions
print("Subsets of [1,2,3]:", subsets([1, 2, 3]))
sols = solve_queens(6)
print("6-Queens solutions:", len(sols), "| first:", sols[0])Key points
- Choose, explore, un-choose
- Prune invalid branches early
- Exponential worst case
- Finds all valid combinations