Backtracking

Build solutions incrementally and undo choices that lead to dead ends — implement permutations, subsets, and N-queens with pruning.

Backtracking is systematic exhaustive search with pruning. You build a candidate solution incrementally — appending one element at a time — and recurse. When the current partial solution violates a constraint, you undo the last choice (backtrack) and try the next option. This avoids generating all candidates explicitly; pruning cuts branches of the search tree early.

The template is always the same:

def backtrack(current, choices):
    if is_complete(current):
        record(current)
        return
    for choice in choices:
        if is_valid(current, choice):
            current.append(choice)    # choose
            backtrack(current, ...)   # explore
            current.pop()             # undo (backtrack)

Three backtracking implementations

Python — editable, runs in your browser

# ── 1. Permutations ──────────────────────────────────────────────────────────
# All orderings of a list of distinct elements.

def permutations(nums):
  result = []
  def backtrack(current, remaining):
      if not remaining:
          result.append(current[:])
          return
      for i in range(len(remaining)):
          current.append(remaining[i])
          backtrack(current, remaining[:i] + remaining[i+1:])
          current.pop()
  backtrack([], nums)
  return result

# ── 2. Subsets ────────────────────────────────────────────────────────────────
# All 2^n subsets (including empty set and full set).
# Use a start index to avoid re-adding earlier elements.

def subsets(nums):
  result = []
  def backtrack(start, current):
      result.append(current[:])      # record at every node, not just leaves
      for i in range(start, len(nums)):
          current.append(nums[i])
          backtrack(i + 1, current)
          current.pop()
  backtrack(0, [])
  return result

# ── 3. N-queens ───────────────────────────────────────────────────────────────
# Place n queens on an n x n board so no two attack each other.
# A queen attacks along rows, columns, and both diagonals.

def n_queens(n):
  solutions = []
  cols  = set()
  diag1 = set()   # row - col is constant on the top-left/bottom-right diagonal
  diag2 = set()   # row + col is constant on the top-right/bottom-left diagonal
  board = [["." for _ in range(n)] for _ in range(n)]

def backtrack(row):
      if row == n:
          solutions.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               # pruning — this column is attacked
          board[row][col] = "Q"
          cols.add(col)
          diag1.add(row - col)
          diag2.add(row + col)
          backtrack(row + 1)
          board[row][col] = "."      # undo
          cols.remove(col)
          diag1.remove(row - col)
          diag2.remove(row + col)

backtrack(0)
  return solutions

# ── Demo ──────────────────────────────────────────────────────────────────────
print("Permutations of [1,2,3]:")
print(permutations([1, 2, 3]))

print()
print("Subsets of [1,2,3]:")
print(subsets([1, 2, 3]))

print()
print(f"4-queens has {len(n_queens(4))} solutions")
print(f"8-queens has {len(n_queens(8))} solutions")

The undo step matters

In permutations: current.pop() undoes the choice before trying the next element at the same position. Without it, current would grow unboundedly and the same elements would appear in multiple branches.

In N-queens: removing col, row - col, and row + col from the sets before returning means the constraints of one column choice do not "leak" into sibling branches.

Pruning is what separates efficient backtracking from blind enumeration. In N-queens the constraint check col in cols eliminates entire sub-trees — no need to try placing queens in attacked positions. The number of valid placements for 8-queens is 92 out of 8^8 = 16,777,216 possible blind placements. Pruning cuts the search tree dramatically.

Subsets vs permutations

Subsets record the partial solution at every recursive node (not just the leaves), because an empty set and every prefix are valid answers. Permutations only record at the leaves (when remaining is empty and the full permutation is built). Both use the same build-recurse-undo skeleton.

Where to go next

Next: lab — paradigm problems — four problems where the first task is identifying which paradigm applies, then implementing it.

Finished reading? Mark it complete to track your progress.

Three backtracking implementations

The undo step matters

Subsets vs permutations

Where to go next

On this page