Recursion & Backtracking — Subsets, Permutations and the Choose–Explore–Unchoose Template

Recursion is a function that solves a problem by calling itself on a smaller version of the same problem. Backtracking is recursion used to explore all choices: try an option, explore further, then undo it and try the next one.

Recursion in two rules

1. Base case — the smallest input you can answer directly (stops the recursion).
2. Recursive case — reduce the problem and trust the function to solve the smaller one.

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

When factorial(4) runs, the calls wait on the call stack: factorial(4) → factorial(3) → factorial(2) → factorial(1). Then the answers return back up: 1 → 2 → 6 → 24. The depth of that stack is the space complexity — here O(n). Forget the base case and you get a stack overflow.

Leap of faith: don't trace every call in your head. Assume f(n−1) works, and only ask: how do I build f(n) from it?

The recursion tree

Calls that branch form a tree. Fibonacci fib(n) = fib(n−1) + fib(n−2) branches twice per call, so naive recursion does about 2ⁿ calls — which is why it's slow, and why dynamic programming (memoisation) exists. Drawing the tree is how you calculate a recursive algorithm's time complexity: (number of nodes) × (work per node).

Backtracking: choose → explore → unchoose

Backtracking builds a solution step by step. At each step:

1. Choose an option and add it to the current path.
2. Explore — recurse to make the next choice.
3. Unchoose — remove it, so the next option starts from a clean state.

Subsets (power set)

Each element is either in or out — 2ⁿ subsets.

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

    def dfs(i):
        if i == len(nums):
            res.append(path[:])          # copy! path keeps changing
            return
        path.append(nums[i])             # choose: include nums[i]
        dfs(i + 1)                       # explore
        path.pop()                       # unchoose
        dfs(i + 1)                       # explore without nums[i]

    dfs(0)
    return res

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(nums, 0, new ArrayList<>(), res);
    return res;
}
void dfs(int[] nums, int i, List<Integer> path, List<List<Integer>> res) {
    if (i == nums.length) { res.add(new ArrayList<>(path)); return; }
    path.add(nums[i]);                 // choose
    dfs(nums, i + 1, path, res);       // explore
    path.remove(path.size() - 1);      // unchoose
    dfs(nums, i + 1, path, res);
}

Time O(n · 2ⁿ) (2ⁿ subsets, copying each takes up to n).

Permutations

Order matters, so at each step choose any unused element.

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

    def dfs():
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True; path.append(nums[i])     # choose
            dfs()                                    # explore
            path.pop(); used[i] = False              # unchoose
    dfs()
    return res

n! permutations → O(n · n!) time.

Combination Sum (reuse allowed)

Pick numbers (each can be reused) that add up to target. Pass a start index so you don't produce the same combination in a different order, and prune when the sum goes over.

def combination_sum(candidates, target):
    res, path = [], []

    def dfs(start, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remaining:
                continue                  # prune this branch
            path.append(c)
            dfs(i, remaining - c)         # i (not i+1): same number can repeat
            path.pop()
    dfs(0, target)
    return res

Handling duplicates (Subsets II, Combination Sum II): sort first, and skip nums[i] when it equals nums[i−1] at the same level of the loop (i > start).

Bigger example: N-Queens

Place N queens so that no two attack each other. Go row by row; for each column, check whether the column and both diagonals are free; place, recurse to the next row, then remove.

Track used columns and diagonals in sets: a diagonal is identified by row − col, the anti-diagonal by row + col. Each check is then O(1), and pruning makes the search fast enough for typical N.

How to recognise backtracking

• "Generate all subsets / permutations / combinations / partitions."
• "Find every way to…", "is there any arrangement…" with small input (n ≤ ~20).
• Puzzles: N-Queens, Sudoku, word search in a grid.

Common mistakes

1. Appending path itself instead of a copy — every result ends up as the same (empty) list.
2. Forgetting to unchoose — state leaks between branches.
3. Missing the base case → infinite recursion / stack overflow.
4. Producing duplicates: use a start index for combinations, sort + skip for duplicate inputs.

Key takeaways

• Recursion = base case + smaller subproblem; its space = maximum call depth.
• Backtracking template: choose → explore → unchoose.
• Expect exponential time (2ⁿ, n!); prune early to stay fast.