Backtracking

Backtracking is systematic trial and error. Build a solution step by step, and when you hit a dead end, undo the last step and try something else. It's like exploring a maze - when a path doesn't work, you backtrack.

The Core Idea

Make a choice, explore what happens, then undo that choice and try another. This naturally maps to recursion: each function call makes one choice, and returning "undoes" it.

The Template

def backtrack(path, choices):
    if is_solution(path):
        result.append(path[:])  # Found one!
        return

    for choice in choices:
        if is_valid(choice):
            path.append(choice)       # Make choice
            backtrack(path, choices)  # Explore
            path.pop()                # Undo choice

Classic: Generate Permutations

def permute(nums):
    result = []

    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return

        for i, num in enumerate(remaining):
            path.append(num)
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()

    backtrack([], nums)
    return result

Classic: Subsets

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])

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

    backtrack(0, [])
    return result