Backtracking

Backtracking is a depth-first search technique that builds a solution step by step and abandons (undoes) a partial choice as soon as it can’t lead to a valid complete solution.

What it is

Backtracking explores possible paths to a solution one step at a time. When a path reaches a dead end, you undo the last step and try a different option. Think of every problem as a decision tree. The root is an empty answer. Each level is a decision. Each branch is one option.

When to use it

Use backtracking when you must generate all valid solutions or evaluate all combinations. Do not use it when you need only one solution or the optimal solution. For those, use greedy or dynamic programming. Backtracking has exponential time complexity.

The four components

Every backtracking problem has the same parts:

1. Base case — when to save the current path and stop.
2. Choices — the options at each step.
3. Constraints — the rules that reject an invalid path early.
4. Backtrack step — undo the last choice and try the next one.

The template

def solve(data):
    result = []
    path = []

    def backtrack(index):
        # 1. Base case
        if is_complete(index, path):
            result.append(path[:])  # copy — lists are passed by reference
            return

        # 2. Choices
        for choice in get_choices(index, data):
            # 3. Constraints
            if not is_valid(choice, path):
                continue

            path.append(choice)    # make the choice
            backtrack(index + 1)   # explore
            path.pop()             # 4. Backtrack

    backtrack(0)
    return result

Steps to apply the template

1. Draw the decision tree for a small input. Name each level and each branch.
2. Write the base case. Ask: when is the path complete?
3. Write the choices. Ask: what can I add at this level?
4. Write the constraints. Ask: what makes a path invalid? Reject it before recursion.
5. Add the backtrack step. Pop what you appended.
6. Copy the path when you save it. Never append the same list reference.

Four problems, one template

Subsets

Choice: include or skip each number. No constraint. Base case: index equals list length.

def subsets(nums):
    result, path = [], []

    def backtrack(i):
        if i == len(nums):
            result.append(path[:])
            return
        path.append(nums[i])   # include
        backtrack(i + 1)
        path.pop()
        backtrack(i + 1)       # skip

    backtrack(0)
    return result

Permutations

Same choices as subsets. Constraint: do not reuse a number already in the path. Base case: path length equals list length.

def permute(nums):
    result, path = [], []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result

Combinations

Same as subsets. Change one line: save the path only when its length equals k.

def combine(n, k):
    result, path = [], []

    def backtrack(start):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1)
            path.pop()

    backtrack(1)
    return result

N-Queens

Choice: which column to place the queen in the current row. Constraint: no shared column or diagonal. Base case: n queens placed. Backtrack: remove the last queen.

def solve_n_queens(n):
    result, cols = [], []
    used_cols, diag1, diag2 = set(), set(), set()

    def backtrack(row):
        if row == n:
            result.append(cols[:])
            return
        for col in range(n):
            if col in used_cols or row - col in diag1 or row + col in diag2:
                continue
            cols.append(col)
            used_cols.add(col); diag1.add(row - col); diag2.add(row + col)
            backtrack(row + 1)
            cols.pop()
            used_cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

    backtrack(0)
    return result

Common mistakes

• You append the path list itself instead of a copy. The result fills with empty lists.
• You forget to pop. The path grows and never resets.
• You check constraints after recursion instead of before. You waste time on dead paths.
• You use backtracking when you need only one answer. Use greedy or DP instead.