Data Structures & Algorithms Cheatsheet

Recursion and Backtracking

Use this Data Structures & Algorithms reference while you build software engineering projects, review code, or refresh the syntax you reach for most.

When To Reach For This

Backtracking is exhaustive search with pruning. Build a partial candidate, recurse, then undo the last choice and try the next one. Reach for it when you must enumerate rather than count or optimize.

Signals in a problem statement:

"Return all" or "list every" solution, not just the count or the best one. Counting is usually DP, enumeration is backtracking.
The words permutations, combinations, subsets, partitions, or arrangements.
Constraint satisfaction: place N queens, fill a Sudoku grid, color a map, satisfy a set of rules.
Very small constraints. n ≤ 8 for permutations, n ≤ 20 for subsets, board sizes under 10.
Word or path search in a grid where a cell may be reused across different paths but not within one.
The output itself is exponential, so no polynomial algorithm can exist.

Classic problems it solves:

Subsets and Subsets II
Permutations and Permutations II
Combination Sum, Combination Sum II
N-Queens
Word Search and Word Search II
Palindrome Partitioning
Sudoku Solver
Letter Combinations of a Phone Number
Restore IP Addresses

Complexity

Problem	Time	Space (excluding output)
all subsets of n	O(2ⁿ · n)	O(n)
all permutations of n	O(n! · n)	O(n)
combinations C(n, k)	O(C(n, k) · k)	O(k)
N-Queens	O(n!) with pruning	O(n)
Sudoku (9 × 9)	O(9^m), m = blanks	O(1)
word search in an r × c grid	O(rc · 3^L)	O(L)
palindrome partitioning	O(2ⁿ · n)	O(n)
subsets with a sum target	O(2ⁿ)	O(n)

The · n factor is the cost of copying each completed candidate into the output. Recursion depth, and therefore stack space, is the length of a candidate.

The Universal Template

Every backtracking solution is this shape. The three decisions are the base case, the choice set, and what "undo" means.

def backtrack(state, choices, out):
    if is_complete(state):
        out.append(state[:])            # COPY, state is mutated after
        return
    for c in valid_choices(state, choices):
        state.append(c)                 # choose
        backtrack(state, choices, out)  # explore
        state.pop()                     # UNDO, unconditionally

Three rules that fix most bugs:

Copy on record. out.append(state) stores a live reference that later mutations wreck.
Undo on every exit path, including early returns. Put the pop() after the recursive call, never inside a conditional.
Prune before recursing, not after. A check at the top of the callee still pays for the call.

Subsets And Combinations

def subsets(nums):
    """All 2^n subsets. Each index is include or exclude."""
    out, path = [], []
    def go(i):
        if i == len(nums):
            out.append(path[:])
            return
        go(i + 1)                       # exclude nums[i]
        path.append(nums[i])            # include nums[i]
        go(i + 1)
        path.pop()
    go(0)
    return out

def subsets_start_index(nums):
    """Same result, the start-index idiom. Records at every node."""
    out = []
    def go(start, path):
        out.append(path[:])             # every prefix is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            go(i + 1, path)             # i + 1: no reuse
            path.pop()
    go(0, [])
    return out

def subsets_with_dup(nums):
    """Duplicates in the input. Sort, then skip repeats at the same depth."""
    nums.sort()
    out = []
    def go(start, path):
        out.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                # same value, same level: skip
            path.append(nums[i])
            go(i + 1, path)
            path.pop()
    go(0, [])
    return out

def combinations(n, k):
    """C(n, k) subsets of size k, with a pruning bound."""
    out = []
    def go(start, path):
        if len(path) == k:
            out.append(path[:])
            return
        need = k - len(path)
        for i in range(start, n - need + 2):    # not enough left: stop
            path.append(i)
            go(i + 1, path)
            path.pop()
    go(1, [])
    return out

def combination_sum(candidates, target):
    """Unlimited reuse of each candidate. Note go(i, ...) not go(i + 1, ...)."""
    candidates.sort()
    out = []
    def go(start, path, remain):
        if remain == 0:
            out.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:
                break                   # sorted, so everything after is worse
            path.append(candidates[i])
            go(i, path, remain - candidates[i])    # i allows reuse
            path.pop()
    go(0, [], target)
    return out

i versus i + 1 in the recursive call is the whole difference between reuse and no reuse. i > start is the duplicate skip, and using i > 0 instead wrongly drops valid candidates.

Permutations

def permutations(nums):
    """Swap in place. O(n! * n), O(n) extra."""
    out = []
    def go(k):
        if k == len(nums):
            out.append(nums[:])
            return
        for i in range(k, len(nums)):
            nums[k], nums[i] = nums[i], nums[k]
            go(k + 1)
            nums[k], nums[i] = nums[i], nums[k]    # swap back
    go(0)
    return out

def permutations_used_array(nums):
    """The used-flag idiom, needed once duplicates are involved."""
    out, path = [], []
    used = [False] * len(nums)
    def go():
        if len(path) == len(nums):
            out.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            go()
            path.pop()
            used[i] = False
    go()
    return out

def permute_unique(nums):
    """Duplicates: sort, then only use a repeat if its predecessor is used."""
    nums.sort()
    out, path = [], []
    used = [False] * len(nums)
    def go():
        if len(path) == len(nums):
            out.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue                # enforce one canonical order
            used[i] = True
            path.append(nums[i])
            go()
            path.pop()
            used[i] = False
    go()
    return out

// Java: the same swap-based permutation
void permute(int[] a, int k, List<List<Integer>> out) {
    if (k == a.length) {
        List<Integer> copy = new ArrayList<>();
        for (int x : a) copy.add(x);
        out.add(copy);
        return;
    }
    for (int i = k; i < a.length; i++) {
        swap(a, k, i);
        permute(a, k + 1, out);
        swap(a, k, i);
    }
}

Constraint Satisfaction

Pruning is what makes these tractable. The pattern is a set of "occupied" markers that make a conflict check O(1).

def solve_n_queens(n):
    """O(1) conflict checks via three sets. Diagonals are constant along
    r - c and r + c."""
    out = []
    cols, diag, anti = set(), set(), set()
    placement = []

    def go(r):
        if r == n:
            out.append(["." * c + "Q" + "." * (n - c - 1) for c in placement])
            return
        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)
            placement.append(c)
            go(r + 1)
            placement.pop()
            anti.discard(r + c)
            diag.discard(r - c)
            cols.discard(c)

    go(0)
    return out


def solve_sudoku(board):
    """board is 9x9 of chars, '.' for blank. Mutates in place."""
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    blanks = []
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == ".":
                blanks.append((r, c))
            else:
                rows[r].add(ch)
                cols[c].add(ch)
                boxes[(r // 3) * 3 + c // 3].add(ch)

    def go(i):
        if i == len(blanks):
            return True
        r, c = blanks[i]
        b = (r // 3) * 3 + c // 3
        for d in "123456789":
            if d in rows[r] or d in cols[c] or d in boxes[b]:
                continue
            board[r][c] = d
            rows[r].add(d)
            cols[c].add(d)
            boxes[b].add(d)
            if go(i + 1):
                return True             # a solution exists, stop unwinding
            board[r][c] = "."
            rows[r].discard(d)
            cols[c].discard(d)
            boxes[b].discard(d)
        return False

    go(0)


def word_search(board, word):
    """One word in a grid. Mark and restore the visited cell."""
    rows, cols = len(board), len(board[0])

    def go(r, c, i):
        if i == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]:
            return False
        board[r][c] = "#"               # mark visited
        found = (go(r + 1, c, i + 1) or go(r - 1, c, i + 1)
                 or go(r, c + 1, i + 1) or go(r, c - 1, i + 1))
        board[r][c] = word[i]           # restore
        return found

    return any(go(r, c, 0) for r in range(rows) for c in range(cols))

Returning True up the stack is the difference between "find one solution" and "find all". For one solution, propagate the boolean and stop. For all, ignore the return and keep looping.

Pruning Techniques

Technique	What it does
sort then early `break`	with sorted candidates, once one exceeds the target, so do the rest
feasibility bound	if the remaining items cannot reach the target, return now
duplicate skip at the same depth	`if i > start and a[i] == a[i-1]: continue`
canonical ordering for permutations	`if a[i] == a[i-1] and not used[i-1]: continue`
occupied sets for O(1) conflict checks	N-Queens diagonals, Sudoku rows and columns
memoize on the state	turns backtracking into DP when subproblems repeat
symmetry breaking	fix the first queen to the left half, halve the search
most-constrained variable first	fill the Sudoku cell with the fewest options next

def can_partition_k_subsets(nums, k):
    """Feasibility pruning turns an intractable search into a fast one."""
    total = sum(nums)
    if total % k:
        return False
    target = total // k
    nums.sort(reverse=True)             # big items first, fail faster
    if nums[0] > target:
        return False
    buckets = [0] * k

    def go(i):
        if i == len(nums):
            return True
        seen = set()
        for b in range(k):
            if buckets[b] + nums[i] > target or buckets[b] in seen:
                continue                # skip identical bucket states
            seen.add(buckets[b])
            buckets[b] += nums[i]
            if go(i + 1):
                return True
            buckets[b] -= nums[i]
        return False

    return go(0)

Recursion Fundamentals

Not every recursion is backtracking. Plain recursion has three parts and no undo step.

# 1. base case  2. recurse on a smaller input  3. combine
def power(base, exp):
    """Fast exponentiation, O(log exp). Handle exp < 0 first, because
    -1 // 2 is -1 in Python and the recursion would never terminate."""
    if exp < 0:
        return 1 / power(base, -exp)
    if exp == 0:
        return 1
    half = power(base, exp // 2)
    return half * half * (base if exp % 2 else 1)

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

# tail-recursion-shaped functions convert to loops mechanically
def factorial_iter(n):
    out = 1
    for i in range(2, n + 1):
        out *= i
    return out

Python does not optimize tail calls, so deep tail recursion still overflows. Convert to a loop or raise the limit.

import sys
sys.setrecursionlimit(10 ** 6)     # last resort, the C stack can still crash

Recursion type	Convert to	When
tail recursion	a `while` loop	always mechanical
single-branch recursion	a loop with an accumulator	linear chains, linked lists
tree recursion with repeats	memoization or DP	overlapping subproblems
tree recursion, no repeats	explicit stack	depth is the only issue
mutual recursion	a state machine	parsers

Gotchas

Copy on record. out.append(path) appends a reference. Every entry ends up identical and usually empty.
Undo unconditionally. A pop() skipped on one branch corrupts every later candidate.
i versus i + 1. Passing i allows reuse of the current element, i + 1 forbids it. Passing start unchanged causes infinite recursion.
i > start versus i > 0 in the duplicate skip. Using i > 0 also skips legitimate reuse across depths.
Sort before skipping duplicates. The skip relies on equal values being adjacent.
Restore mutated global state, including grid cells and occupied sets, on every exit path.
Return values in "find one" mode. Forgetting to propagate the boolean makes the search continue after it already succeeded.
Mutable default arguments. def go(path=[]) shares one list across calls in Python. Use None and initialize inside.
Recursion depth. Backtracking depth equals candidate length, which is safe. Plain recursion over a 10⁵-element list is not.
Memoize only pure state. If the function depends on mutable outer state, caching on the arguments alone returns wrong answers.