Algorithms & Coding Interviews · Recursion & Trees

Recursion & Backtracking

Recursion solves a problem through smaller copies of itself; backtracking explores every choice and undoes it before the next. Learn the three questions behind every recursive function, the choose → explore → un-choose template, pruning and duplicate handling, with the subset tree, Combination Sum and N-Queens animated.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 10 min read▶ 3 interactive🛠️ 4 exercises

🎯 What you'll learn

Base case, recursive case and the leap of faith
The backtracking template and its three decisions
Complexity, pruning and duplicate skipping
Six LeetCode problems up to N-Queens

📚 Before you start

Part 1The Pattern

A recursive function solves a problem by solving smaller instances of the same problem. Write it in three parts: a base case that stops, a recursive case that shrinks the input, and a leap of faith: assume the recursive call returns the right answer for the smaller input, and only think about how to combine it. Backtracking is recursion that builds a solution step by step, explores every valid choice at each step, and undoes each choice before trying the next. It's how you generate subsets, permutations, combinations and board placements.

The include/exclude decision tree that generates all subsets

1Writing a Recursive Function

text

def solve(problem):
    if problem is tiny:            # base case: answer directly
        return direct_answer
    sub = solve(smaller(problem))  # trust it works
    return combine(sub, problem)

Questions to answer before coding:

What does the function return for an input? Say it in one sentence ("the max depth of this subtree").
What is the smallest input and its answer (empty tree → 0, empty string → true)?
How does the input shrink each call, so you're sure it reaches the base case?

2The Backtracking Template

typescript

function subsetsTemplate(nums: number[]): number[][] {
  const res: number[][] = [], path: number[] = [];
  const backtrack = (start: number): void => {
    res.push([...path]);                 // record a copy
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);                // choose
      backtrack(i + 1);                  // explore
      path.pop();                        // un-choose
    }
  };
  backtrack(0);
  return res;
}

python

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

    def backtrack(start):
        res.append(path[:])               # record a copy of the current choice list
        for i in range(start, len(nums)):
            path.append(nums[i])          # 1. choose
            backtrack(i + 1)              # 2. explore
            path.pop()                    # 3. un-choose (restore state)

    backtrack(0)
    return res

Every backtracking problem is this template with three decisions:

Decision	Subsets	Permutations	Combination Sum	N-Queens
What is a choice?	include `nums[i]`	place an unused number next	add a candidate (reusable)	queen in a column of this row
When is the path complete?	always record	`len(path) == n`	`remaining == 0`	`row == n`
What prunes a branch?	none	used set	`remaining < 0` (sort to stop early)	column/diagonal attacked

3Complexity of Backtracking

Count the leaves of the decision tree and the work to copy each solution:

subsets: 2ⁿ leaves × O(n) copy → O(n · 2ⁿ)
permutations: n! leaves × O(n) → O(n · n!)
combinations of size k: C(n, k) × O(k)

These are exponential by nature: the output itself is that big. Interviewers care that you prune early (sort candidates and break when they exceed the target) and that you don't copy lists unnecessarily.

4Avoiding Duplicates

When the input has duplicates ([1, 2, 2]), sort first and skip a value equal to its predecessor at the same depth: if i > start and nums[i] == nums[i - 1]: continue. That removes duplicate branches without a hash set of results.

Under the HoodThe Call Stack▾

Each call pushes a stack frame holding its parameters and local variables; returning pops it. Backtracking works because the shared path list is modified on the way down and restored on the way up, exactly mirroring the stack. Deep recursion can overflow: Python's default limit is about 1,000 frames (RecursionError), JavaScript engines allow roughly 10,000 to 25,000 depending on frame size, and .NET throws an uncatchable StackOverflowException around 1 MB of stack. For inputs deeper than a few thousand levels (a linked-list-shaped tree, a long path in a grid), convert to an iterative version with an explicit stack.

⚠️ Common Pitfalls

Appending path instead of a copy (res.append(path)): every result ends up as the same, finally empty list.
Forgetting to undo a choice (missing path.pop() or not unmarking used[i]).
No base case or a base case that's never reached → infinite recursion.
Duplicate results from duplicate inputs: sort and skip at the same depth.
Not pruning: exploring branches that already exceed the target.

📋 Quick Reference

text

recursion: base case → recurse on smaller input → combine (trust the call)
backtrack(state): if complete: record copy; for choice in choices: if valid: choose; backtrack; unchoose
dupes: sort; if i > start and a[i] == a[i-1]: continue
subsets O(n·2^n) · permutations O(n·n!) · stack depth = recursion depth

Part 2Interview Problems

Six problems built on the same choose → explore → un-choose template, from power sets to N-Queens.

1Subsets (LeetCode 78)

🟠 Medium. Return all possible subsets (the power set) of distinct integers nums.

text

nums = [1,2,3] → [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Approach. Backtracking where every node of the decision tree is a valid subset: record the path on entry, then try adding each later element. (Alternative: start from [[]] and, for each number, add it to every existing subset.)

Complexity. O(n · 2ⁿ) time and output space.

typescript

function subsets(nums: number[]): number[][] {
  const res: number[][] = [], path: number[] = [];
  const backtrack = (start: number): void => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1);
      path.pop();
    }
  };
  backtrack(0);
  return res;
}

python

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

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

    backtrack(0)
    return res

2Permutations (LeetCode 46)

🟠 Medium. Return all permutations of distinct integers nums.

text

nums = [1,2,3] → 6 permutations

Approach. At each depth choose any number not yet used (track a used array), recurse, then un-mark it. A path of length n is a complete permutation.

Complexity. O(n · n!) time.

typescript

function permute(nums: number[]): number[][] {
  const res: number[][] = [], path: number[] = [], used = new Array(nums.length).fill(false);
  const backtrack = (): void => {
    if (path.length === nums.length) { res.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true; path.push(nums[i]);
      backtrack();
      path.pop(); used[i] = false;
    }
  };
  backtrack();
  return res;
}

python

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

    def backtrack():
        if len(path) == len(nums):
            res.append(path[:])
            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 res

3Combination Sum (LeetCode 39)

🟠 Medium. Return all unique combinations of candidates (distinct, each usable unlimited times) that sum to target.

text

candidates = [2,3,6,7], target = 7 → [[2,2,3],[7]]

Approach. Sort candidates. Backtrack with a start index (so combinations aren't repeated in a different order) and the remaining target; reuse the same index to allow repetition; break as soon as a candidate exceeds what's left.

Complexity. Exponential in the worst case; pruning keeps it practical.

typescript

function combinationSum(candidates: number[], target: number): number[][] {
  const sorted = [...candidates].sort((a, b) => a - b);
  const res: number[][] = [], path: number[] = [];
  const backtrack = (start: number, remaining: number): void => {
    if (remaining === 0) { res.push([...path]); return; }
    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remaining) break;
      path.push(sorted[i]);
      backtrack(i, remaining - sorted[i]);
      path.pop();
    }
  };
  backtrack(0, target);
  return res;
}

python

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

    def backtrack(start, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remaining:
                break                       # sorted → nothing later fits either
            path.append(c)
            backtrack(i, remaining - c)     # i, not i + 1: reuse allowed
            path.pop()

    backtrack(0, target)
    return res

4Generate Parentheses (LeetCode 22)

🟠 Medium. Generate all well-formed strings of n pairs of parentheses.

text

n = 3 → ["((()))","(()())","(())()","()(())","()()()"]

Approach. Build the string left to right. You may add ( while fewer than n are open, and ) while closes < opens. These two rules prune every invalid prefix, so every leaf is valid.

Complexity. O(4ⁿ / √n) results (the Catalan number), each O(n) to build.

typescript

function generateParenthesis(n: number): string[] {
  const res: string[] = [];
  const backtrack = (path: string, opened: number, closed: number): void => {
    if (path.length === 2 * n) { res.push(path); return; }
    if (opened < n) backtrack(path + "(", opened + 1, closed);
    if (closed < opened) backtrack(path + ")", opened, closed + 1);
  };
  backtrack("", 0, 0);
  return res;
}

python

def generate_parenthesis(n):
    res = []

    def backtrack(path, opened, closed):
        if len(path) == 2 * n:
            res.append(path)
            return
        if opened < n:
            backtrack(path + "(", opened + 1, closed)
        if closed < opened:
            backtrack(path + ")", opened, closed + 1)

    backtrack("", 0, 0)
    return res

5Word Search (LeetCode 79)

🟠 Medium. Return true if word can be traced through horizontally/vertically adjacent cells of board, using each cell at most once.

text

board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = "ABCCED" → true

Approach. DFS from every cell matching word[0]. Mark the cell as visited (temporarily overwrite it), try the four neighbours for the next character, then restore it on the way back: classic backtracking on a grid.

Complexity. O(R · C · 3ᴸ) time for word length L (3 directions after the first step), O(L) stack.

typescript

function exist(board: string[][], word: string): boolean {
  const R = board.length, C = board[0].length;
  const dfs = (r: number, c: number, k: number): boolean => {
    if (k === word.length) return true;
    if (r < 0 || c < 0 || r >= R || c >= C || board[r][c] !== word[k]) return false;
    const saved = board[r][c];
    board[r][c] = "#";
    const found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
    board[r][c] = saved;
    return found;
  };
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (dfs(r, c, 0)) return true;
  return false;
}

python

def exist(board, word):
    R, C = len(board), len(board[0])

    def dfs(r, c, k):
        if k == len(word):
            return True
        if r < 0 or c < 0 or r >= R or c >= C or board[r][c] != word[k]:
            return False
        saved, board[r][c] = board[r][c], "#"        # mark visited
        found = any(dfs(r + dr, c + dc, k + 1) for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
        board[r][c] = saved                          # restore
        return found

    return any(dfs(r, c, 0) for r in range(R) for c in range(C))

6N-Queens (LeetCode 51)

🔴 Hard. Return the number of ways to place n queens on an n×n board so that none attack each other. (LeetCode 51 returns the boards; LeetCode 52 returns the count. The search is identical.)

text

n = 4 → 2   (n = 8 → 92)

Approach. Place one queen per row. A column c in row r is safe if the column, the r − c diagonal and the r + c anti-diagonal are all free; keep three sets for O(1) checks. Recurse to the next row; undo on return.

Complexity. O(n!) time in the worst case, O(n) space.

typescript

function totalNQueens(n: number): number {
  const cols = new Set<number>(), diag = new Set<number>(), anti = new Set<number>();
  const place = (r: number): number => {
    if (r === n) return 1;
    let count = 0;
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || diag.has(r - c) || anti.has(r + c)) continue;
      cols.add(c); diag.add(r - c); anti.add(r + c);
      count += place(r + 1);
      cols.delete(c); diag.delete(r - c); anti.delete(r + c);
    }
    return count;
  };
  return place(0);
}

python

def total_n_queens(n):
    cols, diag, anti = set(), set(), set()

    def place(r):
        if r == n:
            return 1
        count = 0
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue
            cols.add(c); diag.add(r - c); anti.add(r + c)
            count += place(r + 1)
            cols.remove(c); diag.remove(r - c); anti.remove(r + c)
        return count

    return place(0)

🧠 Key takeaways

Define what the function returns, the base case, and how the input shrinks.
Backtracking = choose → explore → un-choose; record a copy of the path.
Exponential by nature (2ⁿ, n!): prune early and sort + skip to avoid duplicates.
Recursion depth = stack usage; convert to an explicit stack for very deep inputs.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_recursion_and_backtracking_exercise_1.py

TS PY

algo_recursion_and_backtracking_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. res.append(path) instead of res.append(path[:]) results in…

Copy the path.

2. Why does Combination Sum recurse with i rather than i + 1?

Same index = reuse.

3. How do you avoid duplicate subsets when nums has duplicates?

Skip at the same depth.

4. Number of leaves when generating permutations of n items?

Each order is a leaf.

Source: algo_recursion_and_backtracking_theory_1.md, algo_recursion_and_backtracking_theory_2.md · generated by tools/build_lessons.py