Backtracking

The idea

Backtracking is DFS over a tree of choices: pick an option, recurse, then undo it and try the next. It enumerates subsets, permutations, combinations, and solves constraint problems (N-Queens, Sudoku, word search). The cost is the number of nodes in the choice tree — exponential — so it’s for small inputs or problems where you prune hard.

The template

def subsets(nums):
    res, path = [], []
    def dfs(start):
        res.append(path[:])              # record (a copy of) the current partial answer
        for i in range(start, len(nums)):
            path.append(nums[i])         # choose
            dfs(i + 1)                   # explore
            path.pop()                   # un-choose (backtrack)
    dfs(0)
    return res

Three lines — choose, explore, un-choose — are the entire pattern. Always append a copy (path[:]) when recording, since path keeps mutating.

The three canonical shapes

The recursion structure differs by what you’re enumerating:

• Subsets — at each index, include or skip; pass start = i + 1 to avoid reusing earlier elements (order doesn’t matter).
• Combinations (choose k, or sum to target) — like subsets but with a target/size and a start index so [1,2] and [2,1] aren’t both produced.
• Permutations — order matters, so iterate all unused elements each level (track a used[] set, no start):

def permutations(nums):
    res, path, used = [], [], [False] * len(nums)
    def dfs():
        if len(path) == len(nums):
            res.append(path[:]); return
        for i in range(len(nums)):
            if used[i]: continue
            used[i] = True; path.append(nums[i])
            dfs()
            path.pop(); used[i] = False
    dfs()
    return res

Pruning (what makes it tractable)

The search space is exponential — cut branches early:

• Skip duplicates — sort first, then if i > start and nums[i] == nums[i-1]: continue (subsets/combinations with duplicates), or skip a duplicate at the same tree level for permutations.
• Bound checks — stop the branch the moment it can’t succeed (remaining target < 0, partial already invalid).
• Constraint propagation — for N-Queens/Sudoku, track attacked columns/diagonals (sets) so invalid placements are O(1) to reject.
• Visited marks — mark/unmark grid cells in place for word search (and restore on backtrack).

Good pruning often turns “times out” into “instant.”

Constraint-satisfaction problems

N-Queens, Sudoku, and graph coloring place items subject to rules. The pattern: try each value for the next slot, check feasibility (ideally incrementally with sets/bitmasks), recurse, and undo. Strong pruning (forward-checking, most-constrained-variable ordering) is the difference between fast and hopeless.

Complexity

Roughly O(nodes in the choice tree × work per node): subsets O(2^n), permutations O(n!), combinations O(C(n,k)). State this and the input bound — it signals you know it’s exponential by nature.

When to use it

The answer is “all valid arrangements,” “does any valid arrangement exist,” or “the best arrangement” and greedy/DP don’t apply: Subsets, Permutations, Combination Sum, Palindrome Partitioning, Generate Parentheses, N-Queens, Sudoku Solver, Word Search.

Pitfalls

• Recording a reference instead of a copy — append path[:].
• Forgetting to undo the choice (state leaks into sibling branches).
• Duplicate results — sort + skip-equal, or use a per-level seen set.
• No pruning — exponential blowup; always look for a feasibility cut.

If the problem asks for a count or an optimum over overlapping subproblems rather than the arrangements themselves, it’s likely DP — see the DP primers.