Other

Backtracking

Timevaries SpaceO(n)

Imagine solving a Sudoku puzzle. You try a number in an empty cell. If it doesn’t violate any rules, you move to the next cell. If you get stuck, you erase your last entry and try a different number. This “try, check, undo” loop is backtracking.

When to use it: Generating all permutations, combinations, or subsets. Solving constraint satisfaction problems (N-Queens, Sudoku). Any problem that says “find all valid configurations.”

Key insight: Build the solution incrementally. At each step, if the partial solution violates a constraint, prune that entire branch — don’t explore further. This is far more efficient than generating all possibilities and filtering.

Common trap: Forgetting to undo your choice before trying the next option. After the recursive call returns, restore the state to what it was before the choice (this is the “backtrack” step).

# General backtracking template
function backtrack(candidate, state):
    if isComplete(candidate):
        result.add(copy(candidate))
        return

    for choice in getChoices(state):
        if isValid(choice, candidate):
            candidate.add(choice)           # make choice
            backtrack(candidate, nextState)  # recurse
            candidate.remove(choice)        # undo choice (backtrack)

# Example: generate all subsets
function subsets(nums):
    result = []
    function backtrack(start, current):
        result.append(copy(current))        # every partial solution is a subset

        for i = start to length(nums) - 1:
            current.append(nums[i])         # choose
            backtrack(i + 1, current)       # explore
            current.pop()                   # un-choose

    backtrack(0, [])
    return result

# Example: N-Queens
function solveNQueens(n):
    result = []
    function backtrack(row, cols, diags, antiDiags, board):
        if row == n:
            result.append(copy(board))
            return
        for col = 0 to n - 1:
            if col not in cols and (row-col) not in diags and (row+col) not in antiDiags:
                placeQueen(board, row, col)
                backtrack(row+1, cols+{col}, diags+{row-col}, antiDiags+{row+col}, board)
                removeQueen(board, row, col)
    backtrack(0, {}, {}, {}, emptyBoard)
    return result

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

    def backtrack(start: int, current: list[int]) -> None:
        result.append(current[:])

        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result


def permutations(nums: list[int]) -> list[list[int]]:
    result = []

    def backtrack(current: list[int], remaining: set[int]) -> None:
        if not remaining:
            result.append(current[:])
            return

        for num in list(remaining):
            current.append(num)
            remaining.remove(num)
            backtrack(current, remaining)
            remaining.add(num)
            current.pop()

    backtrack([], set(nums))
    return result


def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    """Find all unique combinations that sum to target (reuse allowed)."""
    result = []

    def backtrack(start: int, current: list[int], remaining: int) -> None:
        if remaining == 0:
            result.append(current[:])
            return
        if remaining < 0:
            return

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

    backtrack(0, [], target)
    return result


def solve_n_queens(n: int) -> list[list[str]]:
    result = []
    cols = set()
    diags = set()       # row - col
    anti_diags = set()  # row + col

    board = [["." * n] for _ in range(n)]

    def backtrack(row: int) -> None:
        if row == n:
            result.append(["".join(r) for r in board])
            return

        for col in range(n):
            if col in cols or (row - col) in diags or (row + col) in anti_diags:
                continue

            cols.add(col)
            diags.add(row - col)
            anti_diags.add(row + col)
            board[row] = list(board[row][0])
            board[row][col] = "Q"
            board[row] = ["".join(board[row])]

            backtrack(row + 1)

            cols.discard(col)
            diags.discard(row - col)
            anti_diags.discard(row + col)
            board[row] = list(board[row][0])
            board[row][col] = "."
            board[row] = ["".join(board[row])]

    backtrack(0)
    return result

Problem: Given a collection of distinct integers, return all possible permutations.

How would you approach this?

Answer: This is backtracking. At each position, try each unused number, recurse to fill the next position, then undo the choice (remove the number, mark it as available). The recursion tree explores all orderings.

Problem: Given an array of distinct integers and a target, find all unique combinations where the chosen numbers sum to the target. Each number may be used multiple times.

How would you approach this?

Answer: This is backtracking with pruning. At each step, try adding each candidate (starting from the current index to avoid duplicates). If the running sum exceeds the target, prune that branch. If it equals the target, record the combination.

Time: varies by problem. Subsets: O(2^n) since there are 2^n subsets. Permutations: O(n!) since there are n! orderings. N-Queens: O(n!) in the worst case. The power of backtracking is pruning — the actual runtime is often much less than the theoretical worst case.

Space: O(n) for the recursion stack and the current candidate, where n is the depth of the decision tree (number of choices to make). The output itself may be exponential but is not counted in auxiliary space.