本文最后更新于：2025年11月29日下午

🧩 递归与回溯 —— 把混乱的搜索变成可控的艺术

“回溯不是暴力，而是可控的暴力。” ——算法竞赛圈的祖传名言

当你面对 “所有可能组合” 这一类题时：

所有排列？
所有子集？
所有路径？
所有放置方式？
N 皇后问题？
字符串分割？
数独？

你会发现它们都属于同一类问题： 在一棵概念上的递归树里寻找所有可能解。

这一周，我们将统一它们的思维模型，形成一个：

可以解决 90% 回溯题的通用框架。

🧭 一、回溯是什么？

一句话：

回溯 = 在一棵「隐式树」上做 DFS 搜索 + 按需撤销选择

你可以把回溯看作“带撤销功能的递归 DFS”。

所有回溯问题，都对应一棵类似这样的树：

              []
         /     |      \
       [1]    [2]    [3]
      /  \     ...
  [1,2] [1,3]
...

每一层表示“决策点”，每个分支表示“当前决策”。

🧩 二、回溯的三段式模板（本章最重要）

所有回溯解法都离不开以下“三段式”：

🔧 回溯模板

void backtrack(状态 cur, 其他参数...) {
    if (满足结束条件) {
        收集结果;
        return;
    }

    for (选择 in 可选列表) {
        做选择;         // ①
        backtrack(新的状态); // ②
        撤销选择;       // ③
    }
}

三步口诀：

做选择 → 递归 → 撤销选择

这 3 步构成回溯的最小原子操作。

🧭 三、回溯的三大核心问题模型

你会发现，所有回溯题都来自以下三类：

返回类型	问题分类	LeetCode 举例
所有子集	subset 问题	#78
所有排列	permutation 问题	#46
所有组合	combination 问题	#77、#39
路径搜索	DFS/路径回溯	#17 电话号码组合、#51 N皇后
匹配/切割	分割类问题	#131 分割回文串

通过本周学习，你将能够：

写出所有上述题目的模板化版本
理解“为什么这样写不会重复、不会死循环、不会遗漏”

🌱 四、经典示例一：子集问题（Subsets）

输入：

1	`[1, 2, 3]`

输出：

所有子集：

[
  [], 
  [1], [2], [3],
  [1,2], [1,3], [2,3],
  [1,2,3]
]

🧠 思维过程

每个元素有两种可能：

要
不要

从树形思想看：

             []
        /           \
      [1]           []
   /      \      /      \
[1,2]   [1]   [2]        []
...

💻 C++ 实现

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void backtrack(vector<int>& nums, int start) {
        res.push_back(path); // 所有节点都是解

        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]);         // ① 做选择
            backtrack(nums, i + 1);          // ② 递归
            path.pop_back();                 // ③ 撤销选择
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        backtrack(nums, 0);
        return res;
    }
};

🎯 关键点

对于子集问题：树上的每个节点都是一个合法解
start 控制“不回头”，避免重复

🌿 五、经典示例二：排列问题（Permutations）

输入

[1,2,3]

输出

所有排列：

[1,2,3]
[1,3,2]
[2,1,3]
...

🧠 思维模型

每一层选择一个还没用过的数：

       []
  /     |     \
[1]   [2]    [3]
/ \    ...

💻 C++ 实现

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used;

    void backtrack(vector<int>& nums) {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;

            used[i] = true;           // ①
            path.push_back(nums[i]);
            backtrack(nums);
            path.pop_back();          // ③
            used[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        used.assign(nums.size(), false);
        backtrack(nums);
        return res;
    }
};

🎯 关键要点

使用 used[] 数组防止重复使用同一元素
排列问题需要“占用”与“释放”

🌿 六、经典示例三：组合（Combination）

例题： 组合总和（Combination Sum） #39

输入

1	`candidates = [2,3,6,7], target = 7`

输出

1	`[ [7], [2,2,3] ]`

🧠 核心思想

组合与子集类似，但加入“剪枝”逻辑：

不回头（start 控制）
如果当前和超 target，提前停止 → 剪枝

💻 C++ 实现

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void backtrack(vector<int>& cand, int start, int target) {
        if (target == 0) {
            res.push_back(path);
            return;
        }
        if (target < 0) return;

        for (int i = start; i < cand.size(); i++) {
            path.push_back(cand[i]);
            backtrack(cand, i, target - cand[i]); // 允许重复使用
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& cand, int target) {
        backtrack(cand, 0, target);
        return res;
    }
};

👑 七、经典示例四：N 皇后（N-Queens）——回溯的巅峰手术刀

问题：

在 N×N 棋盘上放置 N 个皇后使其互不攻击。

核心约束：

同列不能放
主对角线不能放
副对角线不能放

💻 C++ 回溯模板

class Solution {
public:
    vector<vector<string>> res;
    vector<string> board;
    vector<bool> col, diag1, diag2;

    void backtrack(int row, int n) {
        if (row == n) {
            res.push_back(board);
            return;
        }

        for (int c = 0; c < n; c++) {
            if (col[c] || diag1[row+c] || diag2[row-c+n-1])
                continue;

            col[c] = diag1[row+c] = diag2[row-c+n-1] = true;
            board[row][c] = 'Q';

            backtrack(row + 1, n);

            col[c] = diag1[row+c] = diag2[row-c+n-1] = false;
            board[row][c] = '.';
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        col.assign(n, false);
        diag1.assign(2*n, false);
        diag2.assign(2*n, false);
        board.assign(n, string(n, '.'));

        backtrack(0, n);
        return res;
    }
};

🧠 精华

N 皇后本质是“剪枝最强的回溯问题”。

通过三组布尔数组实现 O(1) 检查冲突
回溯树会被大量剪枝，否则是 N! 的维度

📈 八、回溯复杂度分析（递归树视角）

尽管回溯很优雅，但其复杂度往往是指数级：

子集 → 2^n
排列 → n!
组合 → C(n, k)
N 皇后 → 比阶乘略小，但近似指数

回溯的关键是：

剪枝越强 → 实际搜索空间越小 → 越能过题。

🧠 九、回溯题通用问法（面试常见）

面试官经常会问：

1️⃣ 如何避免重复？

start 参数（组合 / 子集）
used[] 数组（排列）

2️⃣ 如何优化剪枝？

数组排序后提前 break
条件检查前置
使用额外数据结构快速冲突检测（如 N 皇后）

3️⃣ 为什么需要“撤销选择”？

因为回溯不是树状结构，而是“深度优先 + 回退”，撤销选择是构建正确路径的必要步骤。

🧠 十、思考题与练习

为什么子集问题中，所有节点都可以加入结果，而排列问题只有叶子层是答案？
使用回溯解决以下问题：
- 电话号码字母组合（#17）
- 分割回文串（#131）
- 全排列 II（含重复元素）（#47）
尝试解释 为什么 N 皇后能用 O(1) 判断冲突？
设计一个回溯算法，找出棋盘上所有可能的“骑士巡逻路径”。

🌱 十一、延伸阅读

MIT 6.006：Backtracking & Search
《算法导论》回溯法章节
回溯与 DFS 的本质差异探讨

✨ 十二、总结

本周我们形成了对回溯最核心的理解：

回溯核心	描述
本质	DFS 搜索所有可能的路径
核心结构	做选择 → 递归 → 撤销选择
分类	子集 / 排列 / 组合 / 路径搜索
关键参数	used[] / start / 剪枝
难点	状态恢复、去重、剪枝设计
典型问题	N 皇后、分割回文串、全排列、组合总和