Backtracking

Concept

Backtracking builds a solution step by step. At each step you choose an option, recurse, then undo the choice (backtrack) and try the next option.

Template: if the partial solution is complete, record it; otherwise loop over choices, skip invalid ones (pruning), apply, recurse, undo.

Pruning is what makes backtracking practical: cut off branches that can never lead to a valid answer as early as possible.

Complexity

Code (Python)

def subsets(nums):
    res, path = [], []
    def dfs(i):
        if i == len(nums):
            res.append(path[:])
            return
        path.append(nums[i]); dfs(i + 1)   # take
        path.pop();           dfs(i + 1)   # skip
    dfs(0)
    return res

def solve_n_queens(n):
    cols, d1, d2, board, res = set(), set(), set(), [], []
    def place(r):
        if r == n:
            res.append(["." * c + "Q" + "." * (n - c - 1) for c in board])
            return
        for c in range(n):
            if c in cols or r - c in d1 or r + c in d2:
                continue                   # prune
            cols.add(c); d1.add(r - c); d2.add(r + c); board.append(c)
            place(r + 1)
            cols.remove(c); d1.remove(r - c); d2.remove(r + c); board.pop()
    place(0)
    return res

Remember

• Choose → explore → un-choose.
• Copy the path when recording (path[:]).
• Sort input to skip duplicates easily.