Recursion and Backtracking: The Template

Foundationsmedium15 min
Ask Cairnly about this lesson
On this page

What you will learn

  • Understand the call stack and how recursion builds solutions layer by layer
  • Apply the backtracking template: choose, explore, unchoose
  • Generate permutations, combinations, and subsets using a single pattern
  • Recognize when pruning can drastically reduce the search space

Why this matters

Backtracking powers solutions to combinatorial problems that appear constantly in interviews: permutations, subsets, N-Queens, word search, Sudoku. Once you internalize the template, these problems become mechanical rather than mysterious.

The backtracking template

Every backtracking problem follows the same skeleton:

python
def backtrack(candidates, path, result):
    if is_goal(path):
        result.append(path[:])  # copy the current path
        return
    for choice in candidates:
        if not is_valid(choice, path):
            continue           # prune
        path.append(choice)    # choose
        backtrack(next_candidates, path, result)  # explore
        path.pop()             # unchoose (backtrack)

Subsets (power set)

Generate all subsets of [1, 2, 3].

python
def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])       # every path is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)   # move forward, no repeats
            path.pop()
    backtrack(0, [])
    return result
 
# subsets([1,2,3]) -> [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Time: O(n * 2^n) — 2^n subsets, each up to size n to copy.

Permutations

python
def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()
    backtrack([], nums)
    return result

Time: O(n * n!) — n! permutations, each of length n.

Combination Sum

Find all combinations of candidates that sum to target (elements can be reused).

python
def combination_sum(candidates, target):
    result = []
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break                  # prune: sort first, skip too-large
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # i, not i+1: reuse allowed
            path.pop()
    candidates.sort()
    backtrack(0, [], target)
    return result

The power of pruning

Without pruning, backtracking explores every branch. Adding early termination (like if candidates[i] > remaining: break) can cut the search space by orders of magnitude. Always sort the candidates if it enables pruning.

Recursion vs. iteration

Any recursion can be converted to iteration with an explicit stack, but backtracking is almost always cleaner as recursion. The call stack naturally tracks your "path" of choices.

Quick quiz

Q: In the backtracking template, what does the "unchoose" step (path.pop()) accomplish?

How to explain it in an interview

"I'd use the backtracking template: maintain a current path, iterate over choices, and for each valid choice, add it to the path, recurse, then remove it to backtrack. For subsets I'd add the current path at every node; for permutations I'd add it only at leaf nodes. I always sort the candidates first so I can prune branches early when the remaining target becomes negative."