Backtracking and DFS Search with Pruning

Backtracking explores every candidate solution by building it one decision at a time, recursing on each choice, and undoing the choice before trying the next one. It is how you generate subsets, permutations and combinations, solve puzzles like N-Queens and Sudoku, and enumerate paths in a grid. The search tree is usually exponential, so the craft lies in representing state cheaply, never producing duplicates, and pruning branches that cannot lead to a valid or better answer.

Intuition

Think of the solution as a sequence of decisions: which element comes next, whether to include item i, which column the queen in row r goes to. The decisions form a tree; a depth-first walk over that tree visits every complete solution. At each node you:

1. Check for a finished solution (base case) and record it.
2. Choose one option that is still legal and update the state.
3. Explore the subtree recursively.
4. Un-choose: restore the state exactly as it was, so the next option starts from a clean slate.

The state passed down should contain just enough to make the next decision: in "write n as a non-decreasing sum of at most m parts", that is the remaining sum, the smallest allowed next part, and how many parts are used.

Pruning removes subtrees early:

• Feasibility pruning: stop when the partial solution already violates a constraint (a queen is attacked, the remaining sum is negative, the parts budget is used up).
• Optimality pruning (branch and bound): when minimizing, stop when the cost so far plus an optimistic estimate of the rest cannot beat the best answer found.
• Ordering: try the most promising or most constrained choices first so good answers (and tight bounds) appear early.
• Symmetry and duplicates: sort the input and skip equal choices at the same depth.
• Memoization: if the same sub-state is reached by different paths and the answer depends only on that sub-state, cache it; the search becomes dynamic programming.

When to use it in interviews / OAs

• "Return all subsets / permutations / combinations / partitions / valid strings": the output itself is exponential, so backtracking is the intended solution.
• Constraint puzzles: N-Queens, Sudoku, placing items under rules, word search in a grid.
• Small constraints (n up to about 15 to 20) on an optimization problem with no obvious greedy or DP: search with good pruning.
• Any time you would need a variable number of nested loops.

Template

Choose, explore, un-choose

Write n as a sum of at most max_parts positive integers in non-decreasing order. Requiring each part to be at least the previous one generates every multiset exactly once:

def partitions(n: int, max_parts: int) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []

    def dfs(remaining: int, smallest: int) -> None:
        if remaining == 0:
            result.append(path[:])  # copy: path keeps changing afterwards
            return
        if len(path) == max_parts:
            return  # feasibility pruning: no parts left
        for part in range(smallest, remaining + 1):
            path.append(part)            # choose
            dfs(remaining - part, part)  # explore: next part must be >= part
            path.pop()                   # un-choose

    dfs(n, 1)
    return result

Permutations without duplicates

Sort first. Among equal values, only allow them to be used left to right; this kills every duplicate branch at the source:

def unique_permutations(nums: list[int]) -> list[list[int]]:
    nums = sorted(nums)
    used = [False] * len(nums)
    result: list[list[int]] = []
    path: list[int] = []

    def dfs() -> None:
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue  # an equal value to the left is unused: this order was already tried
            used[i] = True
            path.append(x)
            dfs()
            path.pop()
            used[i] = False

    dfs()
    return result

Subsets without duplicates

Every node of the tree is a subset. Choosing the next element from index start onward avoids reordering; skipping equal values at the same depth avoids duplicates:

def unique_subsets(nums: list[int]) -> list[list[int]]:
    nums = sorted(nums)
    result: list[list[int]] = []
    path: list[int] = []

    def dfs(start: int) -> None:
        result.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue  # same value at the same depth was already explored
            path.append(nums[i])
            dfs(i + 1)
            path.pop()

    dfs(0)
    return result

Constraint search: N-Queens

Place one queen per row. A square is attacked if its column, its diagonal (row - col) or its anti-diagonal (row + col) is taken; sets make each check O(1):

def n_queens(n: int) -> int:
    cols: set[int] = set()
    diag: set[int] = set()
    anti: set[int] = set()

    def place(row: int) -> int:
        if row == n:
            return 1
        count = 0
        for c in range(n):
            if c in cols or row - c in diag or row + c in anti:
                continue  # attacked square
            cols.add(c); diag.add(row - c); anti.add(row + c)
            count += place(row + 1)
            cols.remove(c); diag.remove(row - c); anti.remove(row + c)
        return count

    return place(0)

Paths in a grid: mark and unmark

Find whether a word can be traced through adjacent cells, using each cell at most once. Mark the cell in place while it is on the current path and restore it afterwards:

def exist(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])

    def dfs(r: int, c: int, k: int) -> bool:
        if board[r][c] != word[k]:
            return False
        if k == len(word) - 1:
            return True
        saved, board[r][c] = board[r][c], "#"  # mark as used on this path
        found = any(
            0 <= r + dr < rows and 0 <= c + dc < cols and dfs(r + dr, c + dc, k + 1)
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1))
        )
        board[r][c] = saved  # unmark
        return found

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

Branch and bound

Assign n jobs to n workers (one each) to minimize total time. Start from any valid answer as the bound, and cut a branch when the cost so far plus the cheapest possible cost of the remaining workers already reaches the best answer. Trying cheap jobs first finds good answers early, which makes the bound bite sooner:

def min_assignment_cost(cost: list[list[int]]) -> int:
    n = len(cost)
    best = sum(cost[i][i] for i in range(n))  # a valid assignment is an upper bound
    lower = [0] * (n + 1)  # lower[i] = sum of each remaining worker's cheapest job
    for i in range(n - 1, -1, -1):
        lower[i] = lower[i + 1] + min(cost[i])
    used = [False] * n

    def dfs(worker: int, so_far: int) -> None:
        nonlocal best
        if so_far + lower[worker] >= best:
            return  # optimality pruning
        if worker == n:
            best = so_far
            return
        for job in sorted(range(n), key=lambda j: cost[worker][j]):  # cheap jobs first
            if not used[job]:
                used[job] = True
                dfs(worker + 1, so_far + cost[worker][job])
                used[job] = False

    dfs(0, 0)
    return best

For this particular problem, memoizing on the set of used jobs (a bit mask) gives an O(n * 2^n) DP, and the Hungarian algorithm solves it in O(n^3); the search version shows the pruning pattern you can reuse elsewhere.

Complexity

• The cost is (number of nodes in the search tree) × (work per node). Subsets: 2^n leaves and O(n) to copy each, O(n * 2^n). Permutations: O(n * n!). N-Queens is bounded by n! but pruning makes it far smaller in practice.
• Space: O(depth) for the recursion and the current path, plus the output.
• Pruning does not change the worst-case bound in general, but it often decides whether the search finishes in time.

Common pitfalls

• Appending path instead of path[:]. Every stored answer then points to the same list, which ends up empty.
• Forgetting to undo a change (a used flag, a visited mark, a set entry), or undoing it on only one of several return paths.
• Duplicate answers when the input has repeated values: sort and skip equal siblings, or deduplicate with a set of tuples as a last resort.
• Pruning too aggressively. A bound must be optimistic (a true lower bound when minimizing), otherwise you cut away the optimum.
• Global state leaking between test cases: reset counters and visited arrays per call, or keep them inside the function.
• Underestimating the tree size. Check that n! or 2^n times the per-node work fits the limits before you start.

Interview variations

• Subsets, permutations, combinations (with and without duplicates), combination sum (reuse allowed: recurse with i; no reuse: recurse with i + 1).
• Letter combinations of a phone number, generate parentheses (track open and close counts; never close more than opened).
• Palindrome partitioning and restore IP addresses: choose the next cut position, validate the piece.
• Word search (II uses a trie to search many words at once).
• N-Queens and Sudoku solver: constraint sets or bit masks for O(1) checks.
• Partition into k equal-sum subsets and matchsticks to square: sort descending, prune when a bucket overflows, skip buckets with equal current sums, and memoize on the used-mask.