Recursion & Backtracking Basics: Practice Bridge

                What this page is: a short practice bridge, not a lesson. As a curriculum entry, "Recursion / Backtracking Basics" is already about 65-70% covered by two other guides. This page fills the remaining 30-35% - three worked LeetCode problems - and links you to the rest.
            

1. Introduction & Motivation

Two lessons already cover almost everything a "Recursion / Backtracking Basics" entry would normally contain. Recursion fundamentals - call stacks, base cases, Fibonacci, factorial - live in Part 2: Recursion Complete Guide. The backtracking template and its four foundational applications - Permutations, Subsets, Combination Sum, and N-Queens - live in Part 17: Backtracking & Constraint Search. Together those two guides cover roughly 65-70% of what this topic needs.

This page is the remaining 30-35%: three additional problems that build directly on the template you already know - Combinations, Generate Parentheses, and a fully solved Word Search (the existing lesson only leaves it as an unworked exercise prompt) - plus the complexity bounds for all three and a short set of follow-up exercises. Nothing below repeats recursion basics or the choose-recurse-undo template; it assumes you can already write both from memory.

2. Prerequisites

Read these two lessons first; this page does not repeat them:

Part 2: Recursion Complete Guide - for recursion fundamentals, call-stack tracing, and the Fibonacci/factorial examples that build recursive intuition.
Part 17: Backtracking & Constraint Search - for the generic choose-recurse-undo template and its four foundational applications: Permutations, Subsets, Combination Sum, and N-Queens.

If any of those names are unfamiliar, stop here and read them first. Everything below assumes the template if is_solution: record; for choice: make_choice, recurse, undo_choice is already comfortable, and applies it to three new problems rather than re-deriving it.

3. Combinations (LeetCode 77)

Combinations asks for every way to choose $k$ numbers from $1 \dots n$, order ignored. It is Subsets restricted to a fixed size $k$: the already-covered Subsets problem keeps every branch regardless of length, while Combinations only keeps branches that reach exactly $k$ elements - which is also where the extra pruning below comes from.

Worked Example

Choosing k = 2 from n = 4, by hand

At each call, remain = k - len(path) numbers are still needed. Since only n - i + 1 numbers remain from candidate i onward, any i with n - i + 1 < remain cannot possibly reach size $k$ and is skipped before it is ever tried - the pruning step Subsets does not need.

Path so far	remain	Candidates tried	Result
[]	2	1, 2, 3 (4 pruned - no room left for a second pick)	recurse into each
[1]	1	2, 3, 4	records [1,2], [1,3], [1,4]
[2]	1	3, 4	records [2,3], [2,4]
[3]	1	4	records [3,4]

Six combinations total, matching $\binom{4}{2}=6$.

def combine(n, k):
    """
    LeetCode 77: Combinations
    Choose k numbers from 1..n. Time: O(k * C(n, k)), Space: O(k)
    """
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        remain = k - len(path)
        # Prune: candidate i only works if n - i + 1 >= remain
        for i in range(start, n - remain + 2):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

print(combine(4, 2))
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

// LeetCode 77: Combinations
// Time: O(k * C(n, k)), Space: O(k)
#include <vector>

class Combinations {
public:
    static std::vector<std::vector<int>> combine(int n, int k) {
        std::vector<std::vector<int>> result;
        std::vector<int> path;
        backtrack(n, k, 1, path, result);
        return result;
    }

private:
    static void backtrack(int n, int k, int start, std::vector<int>& path,
                           std::vector<std::vector<int>>& result) {
        if ((int)path.size() == k) {
            result.push_back(path);
            return;
        }
        int remain = k - (int)path.size();
        // Prune: candidate i only works if n - i + 1 >= remain
        for (int i = start; i <= n - remain + 1; ++i) {
            path.push_back(i);
            backtrack(n, k, i + 1, path, result);
            path.pop_back();
        }
    }
};

// LeetCode 77: Combinations
import java.util.*;

class Combinations {
    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(n, k, 1, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int n, int k, int start,
                                   List<Integer> path, List<List<Integer>> result) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        int remain = k - path.size();
        // Prune: candidate i only works if n - i + 1 >= remain
        for (int i = start; i <= n - remain + 1; i++) {
            path.add(i);
            backtrack(n, k, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

4. Generate Parentheses (LeetCode 22)

Generate every well-formed combination of $n$ pairs of parentheses. This is the choose-recurse-undo template with two counters instead of an index: open_count and close_count. Two pruning constraints keep every generated string valid and make the search finish exactly on well-formed strings:

Never let close_count exceed open_count - a closing bracket is only legal once there is an unmatched opening bracket to close.
Stop and record the candidate once its length reaches $2n$ - given the constraint above, that only happens when open_count == close_count == n, so no separate check is needed.

def generate_parenthesis(n):
    """
    LeetCode 22: Generate Parentheses
    Time: O(4^n / sqrt(n)) - the nth Catalan number, Space: O(n)
    """
    result = []

    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            result.append(current)
            return
        if open_count < n:
            backtrack(current + "(", open_count + 1, close_count)
        if close_count < open_count:
            backtrack(current + ")", open_count, close_count + 1)

    backtrack("", 0, 0)
    return result

print(generate_parenthesis(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']

// LeetCode 22: Generate Parentheses
// Time: O(4^n / sqrt(n)), Space: O(n)
#include <string>
#include <vector>

class GenerateParentheses {
public:
    static std::vector<std::string> generate(int n) {
        std::vector<std::string> result;
        std::string current;
        backtrack(n, current, 0, 0, result);
        return result;
    }

private:
    static void backtrack(int n, std::string& current, int openCount, int closeCount,
                           std::vector<std::string>& result) {
        if ((int)current.size() == 2 * n) {
            result.push_back(current);
            return;
        }
        if (openCount < n) {
            current.push_back('(');
            backtrack(n, current, openCount + 1, closeCount, result);
            current.pop_back();
        }
        if (closeCount < openCount) {
            current.push_back(')');
            backtrack(n, current, openCount, closeCount + 1, result);
            current.pop_back();
        }
    }
};

// LeetCode 22: Generate Parentheses
import java.util.*;

class GenerateParentheses {
    public static List<String> generate(int n) {
        List<String> result = new ArrayList<>();
        backtrack(n, new StringBuilder(), 0, 0, result);
        return result;
    }

    private static void backtrack(int n, StringBuilder current, int openCount,
                                   int closeCount, List<String> result) {
        if (current.length() == 2 * n) {
            result.add(current.toString());
            return;
        }
        if (openCount < n) {
            current.append('(');
            backtrack(n, current, openCount + 1, closeCount, result);
            current.deleteCharAt(current.length() - 1);
        }
        if (closeCount < openCount) {
            current.append(')');
            backtrack(n, current, openCount, closeCount + 1, result);
            current.deleteCharAt(current.length() - 1);
        }
    }
}

5. Word Search, Fully Solved (LeetCode 79)

Part 17's exercises list Word Search only as an unworked prompt: "backtrack over grid cells in four directions, marking each visited cell before the recursive call and unmarking it afterward." Here is that idea carried all the way to working code. The state is a grid position (r, c) plus an index into the target word; a cell is visited by swapping its character for a sentinel so the same cell cannot be reused later in the same path, then swapped back - the undo step - on the way out.

def exist(board, word):
    """
    LeetCode 79: Word Search
    Time: O(m * n * 4^L) where L = len(word), Space: O(L) recursion depth
    """
    if not board or not board[0]:
        return False
    rows, cols = len(board), len(board[0])

    def backtrack(r, c, idx):
        if idx == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[idx]:
            return False

        temp = board[r][c]
        board[r][c] = "#"  # mark visited

        found = (backtrack(r + 1, c, idx + 1) or
                 backtrack(r - 1, c, idx + 1) or
                 backtrack(r, c + 1, idx + 1) or
                 backtrack(r, c - 1, idx + 1))

        board[r][c] = temp  # undo
        return found

    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True
    return False

grid = [["A","B","C","E"],
        ["S","F","C","S"],
        ["A","D","E","E"]]
print(exist(grid, "ABCCED"))  # True

// LeetCode 79: Word Search
// Time: O(m * n * 4^L), Space: O(L) recursion depth
#include <vector>
#include <string>

class WordSearch {
public:
    static bool exist(std::vector<std::vector<char>>& board, const std::string& word) {
        if (board.empty() || board[0].empty()) return false;
        int rows = (int)board.size();
        int cols = (int)board[0].size();
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (backtrack(board, word, r, c, 0, rows, cols)) return true;
            }
        }
        return false;
    }

private:
    static bool backtrack(std::vector<std::vector<char>>& board, const std::string& word,
                           int r, int c, int idx, int rows, int cols) {
        if (idx == (int)word.size()) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
        if (board[r][c] != word[idx]) return false;

        char temp = board[r][c];
        board[r][c] = '#';  // mark visited

        bool found = backtrack(board, word, r + 1, c, idx + 1, rows, cols) ||
                     backtrack(board, word, r - 1, c, idx + 1, rows, cols) ||
                     backtrack(board, word, r, c + 1, idx + 1, rows, cols) ||
                     backtrack(board, word, r, c - 1, idx + 1, rows, cols);

        board[r][c] = temp;  // undo
        return found;
    }
};

// LeetCode 79: Word Search
class WordSearch {
    public static boolean exist(char[][] board, String word) {
        if (board.length == 0 || board[0].length == 0) return false;
        int rows = board.length, cols = board[0].length;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (backtrack(board, word, r, c, 0)) return true;
            }
        }
        return false;
    }

    private static boolean backtrack(char[][] board, String word, int r, int c, int idx) {
        if (idx == word.length()) return true;
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return false;
        if (board[r][c] != word.charAt(idx)) return false;

        char temp = board[r][c];
        board[r][c] = '#';  // mark visited

        boolean found = backtrack(board, word, r + 1, c, idx + 1) ||
                        backtrack(board, word, r - 1, c, idx + 1) ||
                        backtrack(board, word, r, c + 1, idx + 1) ||
                        backtrack(board, word, r, c - 1, idx + 1);

        board[r][c] = temp;  // undo
        return found;
    }
}

DFS trace for word "ABCCED" on the 3x4 grid above, starting at (0,0)
Step	Cell (r,c)	Grid char	Word index	Match?	Action
1	(0,0)	A	0	yes	mark visited, recurse toward index 1
2	(0,1)	B	1	yes	mark visited, recurse toward index 2
3	(0,2)	C	2	yes	mark visited, recurse toward index 3
4	(1,2)	C	3	yes	mark visited, recurse toward index 4
5	(2,2)	E	4	yes	mark visited, recurse toward index 5
6	(2,1)	D	5	yes	index reaches 6 = word length -> return True

6. Complexity Analysis

Combinations: the search visits one node per partial combination, so time is $O\!\left(\binom{n}{k}\right)$ up to the $O(k)$ cost of copying each completed path; space is $O(k)$ for the recursion depth and current path.

Generate Parentheses: the number of valid strings of length $2n$ is the $n$th Catalan number, so time is $O(4^n / \sqrt{n})$; space is $O(n)$ for the recursion depth and the string under construction.

Word Search: each of the $m \cdot n$ starting cells can fan out into up to 4 directions at each of the $L$ steps of the word, giving $O(m \cdot n \cdot 4^L)$ time, where $L$ is the word length; space is $O(L)$ for the recursion depth (the grid is marked in place, so no extra visited structure is allocated).

7. Exercises

Easy

Solve LeetCode 216: Combination Sum III - a fixed-size variant of Combination Sum. Choose exactly $k$ digits from 1-9 that sum to a target, combining the size-$k$ stopping condition from Combinations above with Combination Sum's running-sum pruning.

Medium

Solve LeetCode 93: Restore IP Addresses. Backtrack over where to place the three dots in a digit string, pruning any segment that is empty, longer than three digits, over 255, or has a leading zero in a multi-digit segment.

Hard

Solve LeetCode 212: Word Search II. Search for many words in one grid pass by inserting them into a Trie first (see the Trie section of that guide for the structure itself), then backtrack through the grid while walking the Trie instead of comparing against one word at a time, pruning any path whose current prefix has no Trie node.

Mastery challenge: Implement Combination Sum III, Restore IP Addresses, and Word Search II from the exercises above without looking back at this page or Part 17. For each one, name out loud which piece of state the recursion carries (path, counts, or a Trie pointer) and which pruning check rejects a branch before it is fully built.

Review rhythm: tomorrow, reconstruct the Combinations pruning bound and the Generate Parentheses counters without notes; next week, implement Word Search from a blank file; several weeks later, solve Word Search II and check that the Trie genuinely prunes faster than a plain word-by-word search. Finally, teach the "Subsets vs. Combinations" and "Word Search vs. Word Search II" distinctions to someone who only knows the generic backtracking template.

8. Summary Cheat Sheet

This page is a practice bridge, not a full lesson - recursion fundamentals and the backtracking template live in Part 2 and Part 17.
Combinations is Subsets restricted to a fixed size $k$, with an added prune that skips any starting index too close to $n$ to reach $k$ picks.
Generate Parentheses swaps the usual index for two counters, open_count and close_count, and prunes the moment closes would outnumber opens.
Word Search marks a cell visited by swapping in a sentinel character, then swaps the original character back on the way out - no separate visited grid needed.
Complexity bounds: Combinations is $O\!\left(\binom{n}{k}\right)$, Generate Parentheses is $O(4^n / \sqrt{n})$, Word Search is $O(m \cdot n \cdot 4^L)$.
Word Search II extends Word Search with a Trie so many words can be searched in one grid pass instead of one pass per word.

Cookie Consent

Recursion & Backtracking Basics: A Practice Bridge

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. Combinations (LeetCode 77)

Choosing k = 2 from n = 4, by hand

4. Generate Parentheses (LeetCode 22)

5. Word Search, Fully Solved (LeetCode 79)

6. Complexity Analysis

7. Exercises

Easy

Medium

Hard

8. Summary Cheat Sheet

Cookie Consent

Recursion & Backtracking Basics: A Practice Bridge

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. Combinations (LeetCode 77)

Choosing k = 2 from n = 4, by hand

4. Generate Parentheses (LeetCode 22)

5. Word Search, Fully Solved (LeetCode 79)

6. Complexity Analysis

7. Exercises

Easy

Medium

Hard

8. Summary Cheat Sheet

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Part 2: Recursion Complete Guide

Part 17: Backtracking & Constraint Search