Lesson 5 of 10 · 10 min

Recursion and backtracking

Write recursive solutions confidently, and turn 'try every possibility' into a pruned search.

How to write a recursion without getting lost

Three questions settle almost every recursive function. What is the smallest input I can answer immediately? That is the base case. How do I make the problem strictly smaller? That is the progress. And if the recursive call already returns the right answer for that smaller problem, how do I use it?

The third is where people freeze, because they try to trace the whole call tree in their head. You do not need to. Assume the call works, and check only that your combination step is right.

Trusting the recursive call

def max_depth(node):
    if not node:                  # base case: empty tree has depth 0
        return 0
    # assume these two return the correct depths, then combine
    return 1 + max(max_depth(node.left), max_depth(node.right))

Backtracking

Backtracking builds a candidate incrementally and abandons it the moment it cannot lead to a solution. The shape is always the same: make a choice, recurse, then undo the choice so the next branch starts clean.

The undo is what people forget. Without it, the first branch consumes the shared state and every sibling branch sees a corrupted world.

The template

def subsets(nums):
    out, path = [], []

    def backtrack(start):
        out.append(path[:])          # COPY — path is mutated afterwards
        for i in range(start, len(nums)):
            path.append(nums[i])     # choose
            backtrack(i + 1)         # explore
            path.pop()               # un-choose

    backtrack(0)
    return out

Note: Appending `path` instead of `path[:]` makes every result point at the same list, which ends up empty.

Pruning is the whole game

The search space is exponential by nature — 2ⁿ subsets, n! permutations. What makes backtracking usable is abandoning branches early.

In generating valid parentheses, only add a closing bracket when closers used is less than openers used. That single condition restricts the search from all 2^(2n) strings to only the valid ones.

Worth remembering

A correct recursion needs a base case, progress toward it, and trust in the recursive call.
Backtracking is choose, explore, un-choose — forgetting the un-choose is the classic bug.
Python has no tail-call optimisation and a ~1000 frame limit, so deep recursion needs an explicit stack.

Test it now

Backtracking questions cluster in the medium and hard banks.

Medium DSA quiz →All levels