跳到主要内容

递归与回溯

递归（Recursion）是指函数在执行过程中调用其自身以解决问题的编程技巧。回溯（Backtracking）是一种专门通过递归来寻找所有（或部分）可行解的方法。

递归三大要素​

  1. 终止条件：明确函数何时停止调用自身。
  2. 函数定义：明确函数的作用和返回值含义。
  3. 递推关系：明确如何通过规模更小的子问题求解原问题。

经典实例：阶乘与斐波那契​

  • 阶乘：f(n) = n * f(n-1)
  • 斐波那契：f(n) = f(n-1) + f(n-2)

回溯算法​

回溯的思想是：走不通就退回一步，换条路再走。其本质是 DFS 的特殊形式。

回溯三部曲​

  1. 参数与返回值：通常返回 void，结果存入全局列表。
  2. 终止条件：通常在到达决策路径的末端或满足约束时。
  3. 选择与撤回 (回溯核心)：
    • 做出的 选择。
    • 递归进入下一层。
    • 撤销 该次选择（“剪枝”）。
public void backtracking(String res, List<String> list) {
    if (满足终止条件) {
        list.add(res);
        return;
    }
    for (int i = 0; i < n; i++) {
        if (不满足选择条件) continue; // 剪枝
        做出选择;
        backtracking(res + choices[i], list);
        撤回选择;
    }
}

回溯常见模型：子集 (Subsets)​

子集问题通常在每一步都要将当前路径加入结果，而不是仅在叶子节点。

public void findSubsets(int start, List<Integer> path) {
    res.add(new ArrayList<>(path)); // 每一层都是一个子集
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        findSubsets(i + 1, path); // 从 i + 1 开始，避免重复选择
        path.remove(path.size() - 1);
    }
}

经典回溯问题​

1. 全排列 (Permutations)​

给定 [1,2,3]，其全排列有 3! = 6 种。需要使用 boolean[] used 数组标记已选过的数字。

2. 组合总和 (Combination Sum)​

给定数字集合 SS 和目标 TT，寻找和为 TT 的所有数字组合。

3. N 皇后问题 (N-Queens)​

要求在 n×nn \times n 的棋盘上放置 nn 个皇后，使其彼此不能攻击。

剪枝优化 (Pruning)​

通过某些规律提前判断当前分支不可行而跳过，极大缩短搜索时间。

  • 排序 是回溯剪枝的常用前置步骤（如排列组合中的去重）。

练习​

  1. LeetCode 46/47：全排列 I/II (去重关键)
  2. LeetCode 77：组合
  3. LeetCode 39/40：组合总和 I/II (剪枝练习)
  4. LeetCode 78/90：子集 I/II (理解各种回溯模型)
  5. LeetCode 51：N 皇后
  6. LeetCode 22：括号生成
  7. 实现一个经典的 八皇后问题 解法。