Backtracking: Permutations, Combinations, and Pruning

Terminology

Term	Definition
Backtracking	A recursive algorithm that builds solutions incrementally, abandoning ("backtracking" from) partial solutions as soon as they violate a constraint.
Decision tree	A conceptual tree where each node represents a choice point. Backtracking performs a depth-first traversal of this tree.
Pruning	Cutting off branches of the decision tree early when a partial solution cannot lead to a valid complete solution. Reduces the effective search space.
Permutation	An ordered arrangement of $n$ elements. There are $n!$ permutations of $n$ distinct elements.
Combination	An unordered selection of $k$ elements from $n$. There are $\binom{n}{k}$ combinations.

Subset (power set) Any selection of elements from a set, including the empty set. A set of $n$ elements has $2^n$ subsets. State space The set of all possible partial and complete solutions. Backtracking explores this space systematically without revisiting states. Constraint satisfaction A problem where the solution must satisfy a set of constraints (e.g., no two queens attack each other). Backtracking checks constraints at each step.

What & Why

Backtracking is the systematic way to explore all possible solutions to a combinatorial problem. It builds candidates one choice at a time, and whenever a partial candidate cannot possibly lead to a valid solution, it abandons that path and tries the next option.

Think of it as a depth-first search on a decision tree. At each level, you make a choice (include this element, place a queen here, assign this digit). If the choice leads to a dead end, you undo it and try the next option. This "choose, explore, unchoose" pattern is the backbone of backtracking.

The three classic problem families are:

Permutations: arrange all elements in every possible order ( $n!$ results)
Combinations: choose $k$ elements from $n$ ( $\binom{n}{k}$ results)
Subsets: generate all possible selections ( $2^n$ results)

Pruning is what makes backtracking practical. Without pruning, you enumerate the entire state space. With good pruning (like checking queen conflicts early in N-Queens), you can cut the search space by orders of magnitude.

How It Works

The Backtracking Template

Every backtracking solution follows the same structure: choose, explore, unchoose.

N-Queens: Pruning in Action

Place queens row by row. Before placing a queen in column $c$ , check that no previously placed queen shares the same column, main diagonal, or anti-diagonal. If the check fails, prune that branch immediately.

Complexity Analysis

Problem	Time	Space	Output Size
Permutations	$O(n \cdot n!)$	$O(n)$ recursion depth	$n!$
Combinations ($k$ from $n$)	$O(k \cdot \binom{n}{k})$	$O(k)$ recursion depth	$\binom{n}{k}$
Subsets	$O(n \cdot 2^n)$	$O(n)$ recursion depth	$2^n$
N-Queens	$O(n!)$ with pruning	$O(n)$	Varies

Without pruning, N-Queens would explore $n^n$ placements. With column and diagonal pruning, the first row has $n$ choices, the second has at most $n-1$, and so on:

$T(n) \leq n \cdot (n-1) \cdot (n-2) \cdots 1 = n!$

Implementation

Permutations

ALGORITHM Permutations(nums, n)
  INPUT: array nums of size n
  OUTPUT: list of all permutations

  result = empty list

  FUNCTION Backtrack(path, used)
    IF LENGTH(path) = n THEN
      result.append(COPY(path))
      RETURN
    END IF

    FOR i = 0 TO n - 1 DO
      IF used[i] THEN CONTINUE

      path.append(nums[i])
      used[i] = TRUE
      Backtrack(path, used)
      path.removeLast()       // unchoose
      used[i] = FALSE
    END FOR
  END FUNCTION

  Backtrack(empty list, array of FALSE size n)
  RETURN result
END

Combinations (k from n)

ALGORITHM Combinations(n, k)
  INPUT: integers n and k
  OUTPUT: list of all k-element combinations from {1..n}

  result = empty list

  FUNCTION Backtrack(start, path)
    IF LENGTH(path) = k THEN
      result.append(COPY(path))
      RETURN
    END IF

    FOR i = start TO n DO
      path.append(i)
      Backtrack(i + 1, path)
      path.removeLast()
    END FOR
  END FUNCTION

  Backtrack(1, empty list)
  RETURN result
END

N-Queens

ALGORITHM NQueens(n)
  INPUT: board size n
  OUTPUT: list of all valid queen placements

  result = empty list
  cols = empty set
  diag1 = empty set    // row - col
  diag2 = empty set    // row + col

  FUNCTION Backtrack(row, queens)
    IF row = n THEN
      result.append(COPY(queens))
      RETURN
    END IF

    FOR col = 0 TO n - 1 DO
      IF col IN cols OR (row - col) IN diag1 OR (row + col) IN diag2 THEN
        CONTINUE    // prune
      END IF

      queens.append(col)
      cols.add(col)
      diag1.add(row - col)
      diag2.add(row + col)

      Backtrack(row + 1, queens)

      queens.removeLast()
      cols.remove(col)
      diag1.remove(row - col)
      diag2.remove(row + col)
    END FOR
  END FUNCTION

  Backtrack(0, empty list)
  RETURN result
END

Real-World Applications

Sudoku solvers: fill cells one at a time, backtracking when a digit violates row, column, or box constraints.
Compiler optimization: register allocation and instruction scheduling explore assignment possibilities with backtracking when conflicts arise.
Route planning: finding all possible paths through a network (e.g., flight itineraries with constraints) uses backtracking with pruning on cost or time.
Puzzle games: crossword generators, maze solvers, and constraint-based puzzle engines all use backtracking as their core search strategy.
Combinatorial testing: generating all valid test input combinations for software testing uses backtracking to enumerate configurations that satisfy constraints.

Key Takeaways

Backtracking follows the "choose, explore, unchoose" template: make a decision, recurse, then undo the decision before trying the next option
Permutations use a "used" array, combinations use a "start index" to avoid duplicates, and subsets use include/exclude branching
Pruning is what makes backtracking practical: checking constraints early avoids exploring entire subtrees of invalid solutions
The decision tree model helps visualize the search space and identify where pruning can cut branches
N-Queens demonstrates the power of pruning: column and diagonal sets reduce $n^n$ to roughly $n!$ explorations