Recursion & Backtracking

Recursion is what you use when a problem is naturally defined in terms of smaller copies of itself. A tree’s height is one plus the height of its taller subtree. A factorial is n times the factorial of n - 1. The code mirrors the idea directly: solve the tiny case, then reduce the big case until it becomes tiny.

Backtracking is recursion with memory of a partial choice. You build one candidate, explore everything that follows from it, then undo the choice so the next branch starts clean. That choose → explore → un-choose rhythm is the core of subsets, permutations, combinations, and many constraint-search problems.

The mental model

Every recursive function needs two pieces:

• Base case — the smallest input you can answer immediately.
• Recursive case — shrink the input and trust that the recursive call solves the smaller problem.

def factorial(n):
    if n <= 1:                 # base case
        return 1
    return n * factorial(n - 1) # recursive case

The runtime keeps unfinished calls on the call stack. factorial(4) waits for factorial(3), which waits for factorial(2), which waits for factorial(1). When the base case returns, the stack unwinds in reverse order. That is why missing base cases crash as recursion-depth errors: the stack never gets a chance to unwind.

The most useful mindset is trust the recursion. Do not mentally inline every call forever. Define what the function promises to return for a smaller input, assume it keeps that promise, and write the one layer that combines those answers.

Backtracking adds a decision tree. Each level represents one decision, each edge is one choice, and each root-to-leaf path is a candidate answer.

def backtrack(state, choices):
    if is_complete(state):
        answers.append(state.copy())
        return

    for choice in choices:
        if not is_valid(choice, state):
            continue

        make(choice, state)       # choose
        backtrack(state, next_choices(choice, choices))
        undo(choice, state)       # un-choose

Pruning is just refusing to walk branches that cannot lead to a valid answer. If the remaining sum is negative, stop. If a permutation already used a number, skip it. Good backtracking is not brute force with recursion syntax; it is systematic search plus early exits.

Pattern recognition

Variations

Worked problems

Each solution below is the same skeleton wearing a different set of choices. Name the decision at each level before you write code.

def subsets(nums):
    ans = []
    path = []

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

    backtrack(0)
    return ans

def permute(nums):
    ans = []
    path = []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            ans.append(path.copy())
            return

        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return ans

def combination_sum(candidates, target):
    candidates.sort()
    ans = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            ans.append(path.copy())
            return

        for i in range(start, len(candidates)):
            x = candidates[i]
            if x > remaining:
                break
            path.append(x)
            backtrack(i, remaining - x)
            path.pop()

    backtrack(0, target)
    return ans

The classic pitfall