【Gear 2】递归与回溯：暴力的优雅形态

Gear 2 的本质不是蛮力，是把循环系统的血液加压、用更高的密度输出能量。递归与回溯也是如此——表面是暴力枚举所有可能，内核是对搜索树的系统性剪枝，把指数级可能压缩到只遍历真正有意义的分支。

一、递归的三要素

每一个递归函数必须明确：

定义：这个函数做什么，返回什么
base case：什么时候停止递归
递推关系：如何把大问题分解成小问题

// 斐波那契（带记忆化）
int fib(int n, int[] memo) {
    if (n <= 1) return n;                         // base case
    if (memo[n] != 0) return memo[n];             // 已算过，直接返回
    return memo[n] = fib(n-1, memo) + fib(n-2, memo); // 递推
}

没有记忆化的递归会大量重复计算：fib(5) 调用 fib(4) 和 fib(3)，fib(4) 又调用 fib(3)，fib(3) 被计算了两次。加入 memo 后每个子问题只算一次，从 O(2ⁿ) 降到 O(n)。

二、回溯框架

回溯是递归的一种特殊形式：在选择列表中做选择 → 递归进入下一层 → 撤销选择（回溯）。

void backtrack(路径, 选择列表) {
    if 终止条件:
        结果集.add(路径)
        return
    for 选择 in 选择列表:
        做选择（路径.add(选择)）
        backtrack(路径, 缩减后的选择列表)
        撤销选择（路径.removeLast()）
}

这个框架的核心：选择和撤销必须对称，进入递归前加上，从递归返回后减掉，保证每条路径都是干净的。

三、全排列（LeetCode 46）

List<List<Integer>> res = new ArrayList<>();
boolean[] used;

public List<List<Integer>> permute(int[] nums) {
    used = new boolean[nums.length];
    backtrack(nums, new LinkedList<>());
    return res;
}

void backtrack(int[] nums, LinkedList<Integer> path) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path)); // 注意要复制一份
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        path.add(nums[i]);
        used[i] = true;
        backtrack(nums, path);
        path.removeLast();             // 撤销选择
        used[i] = false;
    }
}

搜索树：每层选一个未用过的数字，共 n 层，叶子节点数 = n!（所有排列数）。

四、子集（LeetCode 78）

子集问题：每个元素只有「选」和「不选」两种状态。

List<List<Integer>> res = new ArrayList<>();

public List<List<Integer>> subsets(int[] nums) {
    backtrack(nums, 0, new LinkedList<>());
    return res;
}

void backtrack(int[] nums, int start, LinkedList<Integer> path) {
    res.add(new ArrayList<>(path)); // 每个节点本身就是一个子集
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path); // i+1 确保不重复选
        path.removeLast();
    }
}

start 参数保证每次只从当前位置往后选，避免重复子集（[1,2] 和 [2,1] 只保留一个）。

五、组合（LeetCode 77）

从 n 个数中选 k 个：

List<List<Integer>> res = new ArrayList<>();

public List<List<Integer>> combine(int n, int k) {
    backtrack(n, k, 1, new LinkedList<>());
    return res;
}

void backtrack(int n, int k, int start, LinkedList<Integer> path) {
    if (path.size() == k) {
        res.add(new ArrayList<>(path));
        return;
    }
    // 剪枝：剩余元素不足 k - path.size() 个，直接结束
    for (int i = start; i <= n - (k - path.size()) + 1; i++) {
        path.add(i);
        backtrack(n, k, i + 1, path);
        path.removeLast();
    }
}

剪枝关键：当前位置 i 到 n 的元素数量 n - i + 1 必须 ≥ 还需要的数量 k - path.size()，否则即使全选也凑不够，提前终止。

六、含重复元素的子集（LeetCode 90）

数组有重复数字，子集不能重复。先排序，同层跳过重复数字：

void backtrack(int[] nums, int start, LinkedList<Integer> path) {
    res.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue; // 同层去重
        path.add(nums[i]);
        backtrack(nums, i + 1, path);
        path.removeLast();
    }
}

同层去重 vs 同支去重：i > start 判断的是同一层（同一个 for 循环），如果当前数字和前一个相同说明这条路已经走过了，跳过；但不同层使用相同数字（nums[i] == nums[i-1] 但 i == start）是合法的。

七、N 皇后（LeetCode 51）

在 n×n 的棋盘上放 n 个皇后，使得互不攻击（同行同列同对角线不能共存）：

List<List<String>> res = new ArrayList<>();

public List<List<String>> solveNQueens(int n) {
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    backtrack(board, 0);
    return res;
}

void backtrack(char[][] board, int row) {
    if (row == board.length) {
        res.add(boardToList(board));
        return;
    }
    for (int col = 0; col < board.length; col++) {
        if (!isValid(board, row, col)) continue;
        board[row][col] = 'Q';
        backtrack(board, row + 1);
        board[row][col] = '.';
    }
}

boolean isValid(char[][] board, int row, int col) {
    int n = board.length;
    for (int i = 0; i < row; i++)                                    // 同列
        if (board[i][col] == 'Q') return false;
    for (int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--)     // 左上对角
        if (board[i][j] == 'Q') return false;
    for (int i = row-1, j = col+1; i >= 0 && j < n; i--, j++)      // 右上对角
        if (board[i][j] == 'Q') return false;
    return true;
}

每行只放一个皇后（逐行递归），每次只需检查当前行之上是否有冲突，大幅减少检查量。

八、剪枝的四种常见形式

剪枝类型	场景	代码特征
元素不足	组合类问题	`i <= n - (k - path.size()) + 1`
同层去重	有重复元素	`i > start && nums[i] == nums[i-1]`
约束剪枝	皇后、数独	`isValid()` 函数提前返回
上界剪枝	目标和	当前路径和已超过 target，不再递归

九、递归调用栈深度

回溯的空间复杂度来自递归栈。最坏情况下栈深度 = 解的长度 = n，空间 O(n)。但搜索树的节点总数才是时间复杂度的决定因素，不同问题差异很大：

全排列：O(n × n!)
子集：O(2ⁿ)
N 皇后：O(n!)

Gear 2 让路飞的速度和攻击密度都翻倍，代价是心脏承受更大压力。回溯让你能搜遍所有答案，代价是时间指数级——剪枝就是减轻心脏负担，砍掉不可能出解的分支。

下一站：风车村 · 【橡皮绳的极限】动态规划入门——从记忆化到状态转移