Backtracking Pattern

Backtracking builds a solution incrementally and abandons (backtracks from) a partial solution as soon as it violates the problem's constraints. It is a form of DFS over the space of all possible decisions.

The key operations:

Choose: add a candidate to the current solution.
Explore: recurse with the updated solution.
Unchoose: remove the candidate (backtrack).

Problem: Subsets

Generate all subsets of [1, 2, 3].

def subsets(nums: list[int]) -> list[list[int]]:
    results = []

    def backtrack(start: int, current: list[int]) -> None:
        results.append(list(current))   # every partial solution is a valid subset

        for i in range(start, len(nums)):
            current.append(nums[i])     # choose
            backtrack(i + 1, current)   # explore (no repeats: start = i+1)
            current.pop()               # unchoose

    backtrack(0, [])
    return results

At each call, we record the current state, then try each remaining element, recurse, and undo.

Backtracking Template

def backtrack(state, choices):
    if is_solution(state):
        record(state)
        return

    for choice in choices:
        if is_valid(choice, state):
            make_choice(state, choice)
            backtrack(state, remaining_choices(choices, choice))
            undo_choice(state, choice)

Pruning

Pruning eliminates branches early when the partial solution cannot lead to a valid complete solution:

def combination_sum(candidates, target):
    results = []

    def backtrack(start, current, remaining):
        if remaining == 0:
            results.append(list(current))
            return
        if remaining < 0:
            return   # pruned: sum already exceeded target

        for i in range(start, len(candidates)):
            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])
            current.pop()

    backtrack(0, [], target)
    return results

Without pruning, backtracking exhausts the full search space. Good pruning makes hard problems feasible.

When Do I Use This?

You need to enumerate all valid combinations, permutations, or subsets.
The problem asks for a specific arrangement satisfying constraints (N-Queens, Sudoku).
Keywords: "generate all", "find all combinations", "word search", "palindrome partitioning".

Practice Problems

Done	Question	Difficulty
	Word Search	Medium
	Subsets	Medium
	Generate Parentheses	Medium
	Combination Sum	Medium
	Palindrome Partitioning	Medium
	N-Queens	Hard