Skip to content
Hello Python
5/7

Recursion & Backtracking

Topic 5 of 7, with 3 concept checks. Building solutions incrementally and undoing choices

Define one decision frame, then undo it cleanly

Decision search

Specify the choices available at one recursive frame, the condition that ends a branch, and the exact state restoration required before exploring the next choice.

Core lesson 01

Every correct recursive function needs a base case, a recursive case that breaks the problem into a smaller version of itself, and guaranteed progress toward the base case on every call.

The base case defines the smallest version of the problem you can answer directly. The recursive case expresses the current problem in terms of smaller subproblems, combining their results. The subtle third requirement - genuine progress - is often what causes stack overflows: each recursive call must move strictly closer to a base case.

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

What to remember

What are the three parts every recursive function needs?

Common footguns

  • Writing a recursive case that doesn't actually shrink the problem - guaranteed infinite recursion until a RecursionError.

Core lesson 02

Backtracking builds a solution incrementally: make a choice, recurse to explore what follows, then undo that choice before trying the next option - exploring the full decision tree while reusing the same state.

Where plain recursion often just combines subproblem results, backtracking specifically explores a tree of choices (permutations, combinations, subsets, board configurations) where you mutate shared state, recurse, and then explicitly revert that mutation so the next sibling choice starts clean. That explicit undo step is what distinguishes it from recursion in general.

Python example
def subsets(nums):
    result = []
    path = []
    def backtrack(start):
        result.append(path.copy())      # every path is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])         # choose
            backtrack(i + 1)              # explore
            path.pop()                    # un-choose (backtrack)
    backtrack(0)
    return result

What to remember

What's the core template for backtracking, and how is it different from plain recursion?

Common footguns

  • Appending path directly to result instead of path.copy() - every entry ends up referencing the SAME list, which later mutations then corrupt retroactively.

Core lesson 03

Pruning checks, right after making a choice, whether the current partial state can still lead to a valid solution - backtracking immediately if not, which can turn an exponential-but-hopeless search into a fast one.

Without pruning, backtracking explores the entire decision tree, even obviously invalid branches. Adding a cheap validity check right after each choice - before recursing further - lets you skip that entire subtree immediately, often the difference between a solution that finishes instantly and one that times out.

Python example
def combination_sum(candidates, target):
    result = []
    path = []
    candidates.sort()
    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path.copy())
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:   # PRUNE: sorted, so all later are too big too
                break
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i])
            path.pop()
    backtrack(0, target)
    return result

What to remember

How do you add pruning to backtracking, and why does it matter?

Common footguns

  • Adding a pruning check that relies on sorted order (like the break above) without sorting the input first - silently skips valid branches instead of just invalid ones.

Python lab

Browser Python lab

Runtime · idle

Python loads on your first run. Your code stays in this browser.

Best practices

  • Always make sure recursive calls make genuine progress toward a base case.
  • In backtracking, always undo (pop/remove) a choice after recursing on it.
  • Append path.copy() (or a new list/tuple), never the mutable path itself, when saving a backtracking result.
  • Sort input first when pruning depends on order, and prune as early as possible.

References

LeetCode — Backtracking Explore CardNeetCode — Backtracking Roadmap

Apply the concept in Interview practice

PermutationsmediumLeetCode #46 · O(n·n!) time

Backtrack by swapping elements into place one position at a time.

Open problem
SubsetsmediumLeetCode #78 · O(n·2^n) time

Backtrack including/excluding each element, or iteratively double the result by adding the next element to a copy of every existing subset.

Open problem
Combination SummediumLeetCode #39 · O(2^target) worst case

Backtrack while allowing the same number to be reused, pruning branches once the running sum exceeds the target (as shown above).

Open problem
N-QueenshardLeetCode #51 · O(n!) worst case

Backtrack row by row, placing one queen per row and checking column/diagonal conflicts against queens placed so far before recursing.

Open problem
Word SearchmediumLeetCode #79 · O(rows·cols·4^L) time

DFS/backtrack from every cell matching the first letter, marking visited cells temporarily and un-marking them on backtrack.

Open problem
Generate ParenthesesmediumLeetCode #22 · O(4^n / sqrt(n)) time

Backtrack while tracking open/close counts used so far; only add '(' if opens remain, only add ')' if it wouldn't exceed opens placed so far.

Open problem

Concept checks

Q01

What are the three parts every recursive function needs?

Q02

What's the core template for backtracking, and how is it different from plain recursion?

Q03

How do you add pruning to backtracking, and why does it matter?