尧图网页设计 
前言在算法竞赛和工程面试里有三样东西几乎总是同时出现递归recursion、搜索search、回溯backtracking。初学者常把它们当成三个独立知识点分别去背结果一遇到给一个棋盘问有多少种摆法给你一堆数字问能否凑出目标值这类题就不知道从哪个开始想。真正的原因是这三者不是并列的三样技术而是一条链子上的三个环节。递归是表达方式用自己调用自己来描述一个规模更小、结构相同的子问题。搜索是遍历策略在由所有可能状态构成的状态空间树state space tree上按某种顺序系统地枚举答案。回溯是搜索的剪枝机制走到一条路发现不通时撤销这一步的选择退回到分岔口再试另一条。一句话递归是笔搜索是路回溯是橡皮擦。本文先把这三样拆开讲透再用三个完整可运行的例子迷宫搜索、全排列、N 皇后把它们合起来用。一、递归把大问题交给另一个自己1.1 递归的两个必要条件一个函数要能正确地递归必须同时具备基准情形base case存在一个足够小的问题规模其答案可以直接给出不再递归。递归情形recursive case能把原问题转化为一个或多个规模严格更小的同类问题。缺了基准情形就是无限递归infinite recursion最终栈溢出stack overflow。这不是理论风险Linux 上主线程默认栈大小通常是 8 MB一个栈帧几十到几百字节意味着递归深度大约在一万到十万量级就会崩。1.2 调用栈到底发生了什么写f(3)时计算机并不是跳回去再算一遍而是把当前函数的局部变量、参数、返回地址压入调用栈call stack——这叫栈帧stack frame——再跳转执行触达基准情形后开始返回逐层弹出栈帧。所以递归的空间复杂度至少是递归深度这一点必须刻进直觉里。// recursion_basic.cpp #include iostream #include vector // 阶乘最朴素的线性递归深度 O(n)空间 O(n) long long factorial(int n) { if (n 1) return 1; // 基准情形 return n * factorial(n - 1); // 递归情形 } // 斐波那契反面教材指数级重复计算 O(2^n) long long fib_naive(int n) { if (n 1) return n; return fib_naive(n - 1) fib_naive(n - 2); } // 加上记忆化memoization降为 O(n) long long fib_memo(int n, std::vectorlong long memo) { if (n 1) return n; if (memo[n] ! -1) return memo[n]; // 已经算过直接返回 return memo[n] fib_memo(n - 1, memo) fib_memo(n - 2, memo); } int main() { std::cout 5! factorial(5) \n; // 120 std::cout fib(10) fib_naive(10) \n; // 55 int n 90; std::vectorlong long memo(n 1, -1); std::cout fib(90) fib_memo(n, memo) \n; return 0; }注意memo用引用传递std::vectorlong long 。如果按值传递每一层递归都会拷贝整个数组时间复杂度直接退化成 O(n²) 以上——这是递归中最常见的性能陷阱。任何递归都能改写成迭代用自己的栈模拟改写的最大好处是彻底消除爆栈风险这也是下一篇递推的起点。二、搜索在状态空间上系统地走2.1 状态空间树搜索问题的本质是把所有可能的中间状态组织成一棵树根是初始状态每条边是一次决策叶子是终局搜索就是按某种顺序遍历这棵树。以1 到 n 的全排列为例根是空序列第一层决定第一个位置放哪个数第二层决定第二个……答案在深度为 n 的叶子上。2.2 两种遍历顺序DFS 与 BFS维度深度优先搜索 DFS广度优先搜索 BFS数据结构栈递归天然就是栈队列queue空间复杂度O(深度)O(最宽一层的宽度)能否求最短路一般不能边权为 1 时保证是最短路适合场景判断连通性、枚举所有方案、回溯最短步数、层次遍历、多源扩散实现方式递归最自然必须显式队列选择口诀问题问有多少种方案是否存在→ 用 DFS 回溯问题问最少几步最短距离→ 用 BFS。2.3 一个完整的迷宫搜索地图用字符矩阵表示S是起点E是终点#是墙。// maze.cpp —— 迷宫DFS 找一条路BFS 找最短步数 #include iostream #include queue #include string #include vector static const int DR[4] { -1, 1, 0, 0 }; // 上 下 左 右 static const int DC[4] { 0, 0, -1, 1 }; int R, C; bool in_bounds(int r, int c) { return r 0 r R c 0 c C; } // ---------- DFS只关心能不能到达 ---------- bool dfs(const std::vectorstd::string g, std::vectorstd::vectorbool vis, int r, int c) { if (!in_bounds(r, c) || g[r][c] # || vis[r][c]) return false; if (g[r][c] E) return true; // 找到终点 vis[r][c] true; // 标记已访问防止绕圈 for (int d 0; d 4; d) if (dfs(g, vis, r DR[d], c DC[d])) return true; return false; } // ---------- BFS求从 S 到 E 的最少步数 ---------- int bfs(const std::vectorstd::string g, int sr, int sc) { std::vectorstd::vectorint dist(R, std::vectorint(C, -1)); std::queuestd::pairint, int q; q.push({ sr, sc }); dist[sr][sc] 0; while (!q.empty()) { auto [r, c] q.front(); q.pop(); if (g[r][c] E) return dist[r][c]; // 第一次到达即最短 for (int d 0; d 4; d) { int nr r DR[d], nc c DC[d]; if (!in_bounds(nr, nc) || g[nr][nc] # || dist[nr][nc] ! -1) continue; // 越界 / 墙 / 已访问 dist[nr][nc] dist[r][c] 1; // 入队时即确定距离 q.push({ nr, nc }); } } return -1; // 不可达 } int main() { std::vectorstd::string grid { S..#......, .#.#.####., .#...#...., .####.#.#., ......#..E, }; R static_castint(grid.size()); C static_castint(grid[0].size()); std::vectorstd::vectorbool vis(R, std::vectorbool(C, false)); std::cout DFS reachable : (dfs(grid, vis, 0, 0) ? yes : no) \n; std::cout BFS min steps : bfs(grid, 0, 0) \n; return 0; }两处决定正确性的细节BFS 在入队时就把dist确定下来而不是出队时。同一个节点可能被多个邻居看到如果出队时才写距离就会出现节点重复入队、距离被覆盖的问题。入队即定距是 BFS 的标准写法。DFS 的vis标记在进入时立刻打上否则在网格图中会来回横跳递归永不终止。注意 DFS 这里没有撤销vis。因为问题只问是否存在一条路径走过的格子没必要再走。但只要问题变成枚举所有路径就必须在返回前把vis撤销——这就是第三章要讲的回溯。三、回溯选择、尝试、撤销3.1 回溯的三段式模板void backtrack(State s, ...) { if (满足结束条件) { 记录答案; return; } // 1. 边界 for (每个可选的候选 c : 候选集合) { if (!合法(s, c)) continue; // 2. 剪枝 做出选择(s, c); // 3. 进入 backtrack(s, ...); // 深入 撤销选择(s, c); // 4. 恢复现场 ← 灵魂所在 } }第 4 步恢复现场就是回溯区别于普通 DFS 的唯一标志。一句话概括回溯 DFS 状态撤销。3.2 示例一全排列求{1,2,3}的所有排列每个位置从剩下的数里选一个。// permutations.cpp #include iostream #include vector void backtrack(std::vectorint nums, std::vectorbool used, std::vectorint path, std::vectorstd::vectorint res) { if (path.size() nums.size()) { // 边界每个位置都填满了 res.push_back(path); return; } for (std::size_t i 0; i nums.size(); i) { if (used[i]) continue; // 剪枝这个数已经用了 used[i] true; // 做出选择 path.push_back(nums[i]); backtrack(nums, used, path, res); path.pop_back(); // 撤销选择 used[i] false; // 恢复现场 } } int main() { std::vectorint nums { 1, 2, 3 }; std::vectorbool used(nums.size(), false); std::vectorint path; std::vectorstd::vectorint res; backtrack(nums, used, path, res); for (const auto p : res) { for (int x : p) std::cout x ; std::cout \n; } std::cout total res.size() \n; // 6 return 0; }为什么path用引用传递因为它要在整个递归过程中被共享和修改撤销才有意义。如果按值传每层都是独立副本pop_back撤销的是副本逻辑就散了。3.3 示例二N 皇后在 n×n 棋盘上放 n 个皇后任意两个不能同行、同列、同对角线。关键优化是用三个布尔数组O(1)判断冲突而不是每放一个皇后就扫一遍棋盘列冲突col[c]主对角线左上到右下同一条线上r - c是常数平移后作为下标r - c n - 1副对角线右上到左下同一条线上r c是常数// n_queens.cpp #include iostream #include string #include vector class NQueens { public: explicit NQueens(int n) : n_(n), col_(n, false), diag1_(2 * n, false), diag2_(2 * n, false), board_(n, std::string(n, .)) {} void solve() const { std::cout n n_ , solutions count_ \n; } void run() { backtrack(0); } private: void backtrack(int r) { if (r n_) { // 所有行都摆好了 count_; if (n_ 6) { // 小棋盘打印出来看 for (const auto row : board_) std::cout row \n; std::cout \n; } return; } for (int c 0; c n_; c) { int d1 r - c n_ - 1; int d2 r c; if (col_[c] || diag1_[d1] || diag2_[d2]) continue; // 冲突剪枝 board_[r][c] Q; // 做出选择 col_[c] diag1_[d1] diag2_[d2] true; backtrack(r 1); board_[r][c] .; // 恢复现场 col_[c] diag1_[d1] diag2_[d2] false; } } int n_; int count_ 0; std::vectorbool col_, diag1_, diag2_; std::vectorstd::string board_; }; int main() { for (int n : { 4, 6, 8 }) { NQueens q(n); q.run(); q.solve(); } // n 4, solutions 2 / n 6, solutions 4 / n 8, solutions 92 return 0; }注意backtrack只需要行号作为参数——列、对角线信息全部编码在布尔数组里。这就是用状态换时间否则每放一个皇后都要遍历已放置的皇后列表检查冲突N8 时慢得肉眼可见。3.4 剪枝回溯的性能命脉回溯的时间复杂度是候选方案的组合数暴力枚举往往是指数甚至阶乘级。剪枝pruning就是在搜索树还没长全时砍掉无用的分支。剪枝类型做法效果可行性剪枝当前状态已不可能满足约束立即返回如 N 皇后的三数组判断最优性剪枝当前代价已超过已知最优解最优化问题必用排序剪枝先排序让冲突尽早暴露组合求和类问题记忆化剪枝记录已搜索过的状态有重叠子问题时排序剪枝的经典例子——组合总和从候选数组中选若干个数使和为target每个数可重复用。排序后一旦nums[i] remain就break不是continue因为后面更大for (std::size_t i start; i nums.size(); i) { if (nums[i] remain) break; // ★ 剪枝break 而非 continue path.push_back(nums[i]); backtrack(nums, i, remain - nums[i], path, res); // 传 i 表示可重用 path.pop_back(); }把break误写成continue代码依然能跑出正确结果但退化成完全枚举性能天差地别。这类结果对但慢一万倍的 bug 最难发现。常见坑点坑点 1忘记恢复现场答案数量暴涨或凭空减少❌ 错误写法for (int i 1; i n; i) { if (used[i]) continue; used[i] true; path.push_back(i); backtrack(path, n); // ← 这里忘了 path.pop_back(); used[i] false; }后果第一次走到叶子后返回used全部为true后续所有分支都被continue掉只能得到 1 个排列。反过来若只撤销了used忘了path.pop_back()path会无限增长最终因path.size()永远不等于 n 而递归到爆栈。✅ 正确写法把做出选择和撤销选择写成成对出现的两行中间夹一个backtrack调用这是唯一能靠肌肉记忆保证不漏的办法。used[i] true; path.push_back(i); backtrack(path, n); path.pop_back(); used[i] false; // ★ 与上面严格对称坑点 2递归爆栈❌ 危险场景int dfs(int x) { if (x 0) return 0; return dfs(x - 1) 1; } dfs(1000000); // 栈溢出stack overflow程序直接崩溃即使逻辑正确递归深度一百万也一定会崩Linux 默认单线程栈约 8 MB一个栈帧即使只有 64 字节也只能承受约 13 万层。✅ 三种正确做法改成迭代首选能写循环就别递归用std::stack显式模拟递归把栈搬到堆上加大栈空间Linuxulimit -s 65536Windows 链接时加/STACK:16777216仅限特定平台。还有一个隐蔽的变体——在递归函数里定义大数组void dfs(int d) { int buf[1000000]; // 4 MB 栈帧几层就崩 }✅ 改成static int buf[1000000];全局区或std::vectorint buf(1000000);堆区递归深度就不再受这个数组拖累。坑点 3vis标记该不该撤销搞反了这是最烧脑的一个坑取决于问题类型问题vis是否撤销原因判断连通性 / 是否存在路径❌ 不撤销走过的格子没必要再走撤销反而导致重复搜索枚举所有路径 / 全排列✅ 撤销同一条路径中途的点在别的路径里还要再用求最短路BFS❌ 不撤销每个点只入队一次这是 BFS 正确性的前提❌ 错误写法枚举所有路径却不撤销vis[r][c] true; for (int d 0; d 4; d) if (!vis[nr][nc]) dfs(nr, nc); // 忘了 vis[r][c] false; → 只能找到一条路径✅ 正确写法走到分支末尾时归还vis[r][c] true; for (int d 0; d 4; d) if (!vis[nr][nc]) dfs(nr, nc); vis[r][c] false; // ★ 归还给其它路径使用判断标准很简单问自己这个状态别的分支还需要用它吗需要就撤销不需要就不撤销。坑点 4容器按值传递撤销失效且疯狂拷贝❌ 错误写法void backtrack(std::vectorint nums, std::vectorbool used) { ... }nums、used都是按值拷贝。每一层递归都复制整个数组更要命的是你的pop_back撤销的是副本父层看到的状态根本没变逻辑直接崩掉。✅ 正确写法——需要修改且跨层共享的容器一律传引用void backtrack(const std::vectorint nums, // 只读 → const 引用 std::vectorbool used, // 要改 → 引用 std::vectorint path, // 要改 → 引用 std::vectorstd::vectorint res) // 收集答案 → 引用把const加上还有个额外好处编译器会阻止你在只读参数上误改很多忘记撤销的 bug 会在编译期就被拦下来。坑点 5整数溢出把边界条件判断弄失效搜索中常以累加和是否等于目标作为终止条件如果用int累加❌ 危险写法int sum 0; for (int x : nums) sum x; // nums 里有 1e9 量级的数累加即溢出 if (sum target) ...有符号溢出是未定义行为undefined behavior优化器可能把sum target直接判定为false程序行为完全不可预测。✅ 更根本的做法是在递归参数里传递剩余目标值remain而不是每次都重新求和void dfs(std::size_t start, long long remain) { if (remain 0) { /* 记录答案 */ return; } if (remain 0) return; // 可行性剪枝顺带防溢出检查 for (std::size_t i start; i nums.size(); i) { if (nums[i] remain) break; // 排序后剪枝 path.push_back(nums[i]); dfs(i, remain - nums[i]); // 传下去的是减法不会越滚越大 path.pop_back(); } }传剩余量而不是传累加量天然规避了溢出这是搜索题里的一个重要习惯。坑点 6BFS 出队时才标记visited导致重复入队❌ 错误写法while (!q.empty()) { auto cur q.front(); q.pop(); vis[cur.r][cur.c] true; // ← 太晚了 for (auto nb : neighbors(cur)) if (!vis[nb.r][nb.c]) q.push(nb); // 同一个点可能被 push 很多次 }节点 A 有 5 个邻居同时在队列里它们出队前都把 A 当作未访问于是 A 被重复入队 5 次。数据量大时队列会指数级膨胀内存直接爆炸MLE。✅ 正确写法入队时立刻标记。q.push(start); vis[start.r][start.c] true; // ★ 起点入队即标记 while (!q.empty()) { auto cur q.front(); q.pop(); for (auto nb : neighbors(cur)) { if (vis[nb.r][nb.c]) continue; vis[nb.r][nb.c] true; // ★ 入队前就标记 q.push(nb); } }坑点 7递归不记忆化同一子问题被算了几亿次❌ 反面教材就是本文开头的fib_naive(50)long long fib_naive(int n) { if (n 1) return n; return fib_naive(n - 1) fib_naive(n - 2); // 同一子问题被算了几亿次 }fib(50)会递归约 2^50 ≈ 10¹⁵ 次调用实际根本跑不完fib(40)就要十几秒。✅ 两条路都有效记忆化搜索自顶向下或递推自底向上。long long fib(int n, std::vectorlong long memo) { // 路线 A记忆化 if (n 1) return n; if (memo[n] ! -1) return memo[n]; return memo[n] fib(n - 1, memo) fib(n - 2, memo); }判断是否该加记忆化的方法画出递归树如果发现同一参数组合出现了多次就必须记忆化。这一条也是回溯升级为动态规划dynamic programming的分界线。总结把这三个概念重新串一遍概念一句话定义关键动作典型问题递归用自调用表达更小规模的同类问题写对基准情形阶乘、树遍历、分治搜索在状态空间树上系统枚举选对 DFS / BFS连通性、最短路回溯搜索 撤销遍历所有方案做出选择 / 恢复现场成对写全排列、N 皇后、子集以及三条可以带走的经验递归的空间代价是递归深度。深度可能上万时要么改迭代要么把栈搬到堆上递归函数内绝不放大的局部数组。做出选择和撤销选择必须成对出现中间夹一次递归调用。这是回溯不出错的唯一可靠保证。搜索的性能全在剪枝和状态编码上。用数组把 O(n) 的判断降到 O(1)N 皇后的三个布尔数组用排序把不可能的后续提前break掉——同一个算法剪枝与否能差出好几个数量级。最后递归、搜索、回溯这三剑客之所以总是一起出现是因为它们共享同一个世界观把问题看成一棵树然后决定怎么走、走错了怎么办。想通这一点这三样就不再是需要分别记忆的三个知识点而是同一件事的三种说法。 C++ 递归、搜索与回溯-三剑客
前言在算法竞赛和工程面试里有三样东西几乎总是同时出现递归recursion、搜索search、回溯backtracking。初学者常把它们当成三个独立知识点分别去背结果一遇到给一个棋盘问有多少种摆法给你一堆数字问能否凑出目标值这类题就不知道从哪个开始想。真正的原因是这三者不是并列的三样技术而是一条链子上的三个环节。递归是表达方式用自己调用自己来描述一个规模更小、结构相同的子问题。搜索是遍历策略在由所有可能状态构成的状态空间树state space tree上按某种顺序系统地枚举答案。回溯是搜索的剪枝机制走到一条路发现不通时撤销这一步的选择退回到分岔口再试另一条。一句话递归是笔搜索是路回溯是橡皮擦。本文先把这三样拆开讲透再用三个完整可运行的例子迷宫搜索、全排列、N 皇后把它们合起来用。一、递归把大问题交给另一个自己1.1 递归的两个必要条件一个函数要能正确地递归必须同时具备基准情形base case存在一个足够小的问题规模其答案可以直接给出不再递归。递归情形recursive case能把原问题转化为一个或多个规模严格更小的同类问题。缺了基准情形就是无限递归infinite recursion最终栈溢出stack overflow。这不是理论风险Linux 上主线程默认栈大小通常是 8 MB一个栈帧几十到几百字节意味着递归深度大约在一万到十万量级就会崩。1.2 调用栈到底发生了什么写f(3)时计算机并不是跳回去再算一遍而是把当前函数的局部变量、参数、返回地址压入调用栈call stack——这叫栈帧stack frame——再跳转执行触达基准情形后开始返回逐层弹出栈帧。所以递归的空间复杂度至少是递归深度这一点必须刻进直觉里。// recursion_basic.cpp #include iostream #include vector // 阶乘最朴素的线性递归深度 O(n)空间 O(n) long long factorial(int n) { if (n 1) return 1; // 基准情形 return n * factorial(n - 1); // 递归情形 } // 斐波那契反面教材指数级重复计算 O(2^n) long long fib_naive(int n) { if (n 1) return n; return fib_naive(n - 1) fib_naive(n - 2); } // 加上记忆化memoization降为 O(n) long long fib_memo(int n, std::vectorlong long memo) { if (n 1) return n; if (memo[n] ! -1) return memo[n]; // 已经算过直接返回 return memo[n] fib_memo(n - 1, memo) fib_memo(n - 2, memo); } int main() { std::cout 5! factorial(5) \n; // 120 std::cout fib(10) fib_naive(10) \n; // 55 int n 90; std::vectorlong long memo(n 1, -1); std::cout fib(90) fib_memo(n, memo) \n; return 0; }注意memo用引用传递std::vectorlong long 。如果按值传递每一层递归都会拷贝整个数组时间复杂度直接退化成 O(n²) 以上——这是递归中最常见的性能陷阱。任何递归都能改写成迭代用自己的栈模拟改写的最大好处是彻底消除爆栈风险这也是下一篇递推的起点。二、搜索在状态空间上系统地走2.1 状态空间树搜索问题的本质是把所有可能的中间状态组织成一棵树根是初始状态每条边是一次决策叶子是终局搜索就是按某种顺序遍历这棵树。以1 到 n 的全排列为例根是空序列第一层决定第一个位置放哪个数第二层决定第二个……答案在深度为 n 的叶子上。2.2 两种遍历顺序DFS 与 BFS维度深度优先搜索 DFS广度优先搜索 BFS数据结构栈递归天然就是栈队列queue空间复杂度O(深度)O(最宽一层的宽度)能否求最短路一般不能边权为 1 时保证是最短路适合场景判断连通性、枚举所有方案、回溯最短步数、层次遍历、多源扩散实现方式递归最自然必须显式队列选择口诀问题问有多少种方案是否存在→ 用 DFS 回溯问题问最少几步最短距离→ 用 BFS。2.3 一个完整的迷宫搜索地图用字符矩阵表示S是起点E是终点#是墙。// maze.cpp —— 迷宫DFS 找一条路BFS 找最短步数 #include iostream #include queue #include string #include vector static const int DR[4] { -1, 1, 0, 0 }; // 上 下 左 右 static const int DC[4] { 0, 0, -1, 1 }; int R, C; bool in_bounds(int r, int c) { return r 0 r R c 0 c C; } // ---------- DFS只关心能不能到达 ---------- bool dfs(const std::vectorstd::string g, std::vectorstd::vectorbool vis, int r, int c) { if (!in_bounds(r, c) || g[r][c] # || vis[r][c]) return false; if (g[r][c] E) return true; // 找到终点 vis[r][c] true; // 标记已访问防止绕圈 for (int d 0; d 4; d) if (dfs(g, vis, r DR[d], c DC[d])) return true; return false; } // ---------- BFS求从 S 到 E 的最少步数 ---------- int bfs(const std::vectorstd::string g, int sr, int sc) { std::vectorstd::vectorint dist(R, std::vectorint(C, -1)); std::queuestd::pairint, int q; q.push({ sr, sc }); dist[sr][sc] 0; while (!q.empty()) { auto [r, c] q.front(); q.pop(); if (g[r][c] E) return dist[r][c]; // 第一次到达即最短 for (int d 0; d 4; d) { int nr r DR[d], nc c DC[d]; if (!in_bounds(nr, nc) || g[nr][nc] # || dist[nr][nc] ! -1) continue; // 越界 / 墙 / 已访问 dist[nr][nc] dist[r][c] 1; // 入队时即确定距离 q.push({ nr, nc }); } } return -1; // 不可达 } int main() { std::vectorstd::string grid { S..#......, .#.#.####., .#...#...., .####.#.#., ......#..E, }; R static_castint(grid.size()); C static_castint(grid[0].size()); std::vectorstd::vectorbool vis(R, std::vectorbool(C, false)); std::cout DFS reachable : (dfs(grid, vis, 0, 0) ? yes : no) \n; std::cout BFS min steps : bfs(grid, 0, 0) \n; return 0; }两处决定正确性的细节BFS 在入队时就把dist确定下来而不是出队时。同一个节点可能被多个邻居看到如果出队时才写距离就会出现节点重复入队、距离被覆盖的问题。入队即定距是 BFS 的标准写法。DFS 的vis标记在进入时立刻打上否则在网格图中会来回横跳递归永不终止。注意 DFS 这里没有撤销vis。因为问题只问是否存在一条路径走过的格子没必要再走。但只要问题变成枚举所有路径就必须在返回前把vis撤销——这就是第三章要讲的回溯。三、回溯选择、尝试、撤销3.1 回溯的三段式模板void backtrack(State s, ...) { if (满足结束条件) { 记录答案; return; } // 1. 边界 for (每个可选的候选 c : 候选集合) { if (!合法(s, c)) continue; // 2. 剪枝 做出选择(s, c); // 3. 进入 backtrack(s, ...); // 深入 撤销选择(s, c); // 4. 恢复现场 ← 灵魂所在 } }第 4 步恢复现场就是回溯区别于普通 DFS 的唯一标志。一句话概括回溯 DFS 状态撤销。3.2 示例一全排列求{1,2,3}的所有排列每个位置从剩下的数里选一个。// permutations.cpp #include iostream #include vector void backtrack(std::vectorint nums, std::vectorbool used, std::vectorint path, std::vectorstd::vectorint res) { if (path.size() nums.size()) { // 边界每个位置都填满了 res.push_back(path); return; } for (std::size_t i 0; i nums.size(); i) { if (used[i]) continue; // 剪枝这个数已经用了 used[i] true; // 做出选择 path.push_back(nums[i]); backtrack(nums, used, path, res); path.pop_back(); // 撤销选择 used[i] false; // 恢复现场 } } int main() { std::vectorint nums { 1, 2, 3 }; std::vectorbool used(nums.size(), false); std::vectorint path; std::vectorstd::vectorint res; backtrack(nums, used, path, res); for (const auto p : res) { for (int x : p) std::cout x ; std::cout \n; } std::cout total res.size() \n; // 6 return 0; }为什么path用引用传递因为它要在整个递归过程中被共享和修改撤销才有意义。如果按值传每层都是独立副本pop_back撤销的是副本逻辑就散了。3.3 示例二N 皇后在 n×n 棋盘上放 n 个皇后任意两个不能同行、同列、同对角线。关键优化是用三个布尔数组O(1)判断冲突而不是每放一个皇后就扫一遍棋盘列冲突col[c]主对角线左上到右下同一条线上r - c是常数平移后作为下标r - c n - 1副对角线右上到左下同一条线上r c是常数// n_queens.cpp #include iostream #include string #include vector class NQueens { public: explicit NQueens(int n) : n_(n), col_(n, false), diag1_(2 * n, false), diag2_(2 * n, false), board_(n, std::string(n, .)) {} void solve() const { std::cout n n_ , solutions count_ \n; } void run() { backtrack(0); } private: void backtrack(int r) { if (r n_) { // 所有行都摆好了 count_; if (n_ 6) { // 小棋盘打印出来看 for (const auto row : board_) std::cout row \n; std::cout \n; } return; } for (int c 0; c n_; c) { int d1 r - c n_ - 1; int d2 r c; if (col_[c] || diag1_[d1] || diag2_[d2]) continue; // 冲突剪枝 board_[r][c] Q; // 做出选择 col_[c] diag1_[d1] diag2_[d2] true; backtrack(r 1); board_[r][c] .; // 恢复现场 col_[c] diag1_[d1] diag2_[d2] false; } } int n_; int count_ 0; std::vectorbool col_, diag1_, diag2_; std::vectorstd::string board_; }; int main() { for (int n : { 4, 6, 8 }) { NQueens q(n); q.run(); q.solve(); } // n 4, solutions 2 / n 6, solutions 4 / n 8, solutions 92 return 0; }注意backtrack只需要行号作为参数——列、对角线信息全部编码在布尔数组里。这就是用状态换时间否则每放一个皇后都要遍历已放置的皇后列表检查冲突N8 时慢得肉眼可见。3.4 剪枝回溯的性能命脉回溯的时间复杂度是候选方案的组合数暴力枚举往往是指数甚至阶乘级。剪枝pruning就是在搜索树还没长全时砍掉无用的分支。剪枝类型做法效果可行性剪枝当前状态已不可能满足约束立即返回如 N 皇后的三数组判断最优性剪枝当前代价已超过已知最优解最优化问题必用排序剪枝先排序让冲突尽早暴露组合求和类问题记忆化剪枝记录已搜索过的状态有重叠子问题时排序剪枝的经典例子——组合总和从候选数组中选若干个数使和为target每个数可重复用。排序后一旦nums[i] remain就break不是continue因为后面更大for (std::size_t i start; i nums.size(); i) { if (nums[i] remain) break; // ★ 剪枝break 而非 continue path.push_back(nums[i]); backtrack(nums, i, remain - nums[i], path, res); // 传 i 表示可重用 path.pop_back(); }把break误写成continue代码依然能跑出正确结果但退化成完全枚举性能天差地别。这类结果对但慢一万倍的 bug 最难发现。常见坑点坑点 1忘记恢复现场答案数量暴涨或凭空减少❌ 错误写法for (int i 1; i n; i) { if (used[i]) continue; used[i] true; path.push_back(i); backtrack(path, n); // ← 这里忘了 path.pop_back(); used[i] false; }后果第一次走到叶子后返回used全部为true后续所有分支都被continue掉只能得到 1 个排列。反过来若只撤销了used忘了path.pop_back()path会无限增长最终因path.size()永远不等于 n 而递归到爆栈。✅ 正确写法把做出选择和撤销选择写成成对出现的两行中间夹一个backtrack调用这是唯一能靠肌肉记忆保证不漏的办法。used[i] true; path.push_back(i); backtrack(path, n); path.pop_back(); used[i] false; // ★ 与上面严格对称坑点 2递归爆栈❌ 危险场景int dfs(int x) { if (x 0) return 0; return dfs(x - 1) 1; } dfs(1000000); // 栈溢出stack overflow程序直接崩溃即使逻辑正确递归深度一百万也一定会崩Linux 默认单线程栈约 8 MB一个栈帧即使只有 64 字节也只能承受约 13 万层。✅ 三种正确做法改成迭代首选能写循环就别递归用std::stack显式模拟递归把栈搬到堆上加大栈空间Linuxulimit -s 65536Windows 链接时加/STACK:16777216仅限特定平台。还有一个隐蔽的变体——在递归函数里定义大数组void dfs(int d) { int buf[1000000]; // 4 MB 栈帧几层就崩 }✅ 改成static int buf[1000000];全局区或std::vectorint buf(1000000);堆区递归深度就不再受这个数组拖累。坑点 3vis标记该不该撤销搞反了这是最烧脑的一个坑取决于问题类型问题vis是否撤销原因判断连通性 / 是否存在路径❌ 不撤销走过的格子没必要再走撤销反而导致重复搜索枚举所有路径 / 全排列✅ 撤销同一条路径中途的点在别的路径里还要再用求最短路BFS❌ 不撤销每个点只入队一次这是 BFS 正确性的前提❌ 错误写法枚举所有路径却不撤销vis[r][c] true; for (int d 0; d 4; d) if (!vis[nr][nc]) dfs(nr, nc); // 忘了 vis[r][c] false; → 只能找到一条路径✅ 正确写法走到分支末尾时归还vis[r][c] true; for (int d 0; d 4; d) if (!vis[nr][nc]) dfs(nr, nc); vis[r][c] false; // ★ 归还给其它路径使用判断标准很简单问自己这个状态别的分支还需要用它吗需要就撤销不需要就不撤销。坑点 4容器按值传递撤销失效且疯狂拷贝❌ 错误写法void backtrack(std::vectorint nums, std::vectorbool used) { ... }nums、used都是按值拷贝。每一层递归都复制整个数组更要命的是你的pop_back撤销的是副本父层看到的状态根本没变逻辑直接崩掉。✅ 正确写法——需要修改且跨层共享的容器一律传引用void backtrack(const std::vectorint nums, // 只读 → const 引用 std::vectorbool used, // 要改 → 引用 std::vectorint path, // 要改 → 引用 std::vectorstd::vectorint res) // 收集答案 → 引用把const加上还有个额外好处编译器会阻止你在只读参数上误改很多忘记撤销的 bug 会在编译期就被拦下来。坑点 5整数溢出把边界条件判断弄失效搜索中常以累加和是否等于目标作为终止条件如果用int累加❌ 危险写法int sum 0; for (int x : nums) sum x; // nums 里有 1e9 量级的数累加即溢出 if (sum target) ...有符号溢出是未定义行为undefined behavior优化器可能把sum target直接判定为false程序行为完全不可预测。✅ 更根本的做法是在递归参数里传递剩余目标值remain而不是每次都重新求和void dfs(std::size_t start, long long remain) { if (remain 0) { /* 记录答案 */ return; } if (remain 0) return; // 可行性剪枝顺带防溢出检查 for (std::size_t i start; i nums.size(); i) { if (nums[i] remain) break; // 排序后剪枝 path.push_back(nums[i]); dfs(i, remain - nums[i]); // 传下去的是减法不会越滚越大 path.pop_back(); } }传剩余量而不是传累加量天然规避了溢出这是搜索题里的一个重要习惯。坑点 6BFS 出队时才标记visited导致重复入队❌ 错误写法while (!q.empty()) { auto cur q.front(); q.pop(); vis[cur.r][cur.c] true; // ← 太晚了 for (auto nb : neighbors(cur)) if (!vis[nb.r][nb.c]) q.push(nb); // 同一个点可能被 push 很多次 }节点 A 有 5 个邻居同时在队列里它们出队前都把 A 当作未访问于是 A 被重复入队 5 次。数据量大时队列会指数级膨胀内存直接爆炸MLE。✅ 正确写法入队时立刻标记。q.push(start); vis[start.r][start.c] true; // ★ 起点入队即标记 while (!q.empty()) { auto cur q.front(); q.pop(); for (auto nb : neighbors(cur)) { if (vis[nb.r][nb.c]) continue; vis[nb.r][nb.c] true; // ★ 入队前就标记 q.push(nb); } }坑点 7递归不记忆化同一子问题被算了几亿次❌ 反面教材就是本文开头的fib_naive(50)long long fib_naive(int n) { if (n 1) return n; return fib_naive(n - 1) fib_naive(n - 2); // 同一子问题被算了几亿次 }fib(50)会递归约 2^50 ≈ 10¹⁵ 次调用实际根本跑不完fib(40)就要十几秒。✅ 两条路都有效记忆化搜索自顶向下或递推自底向上。long long fib(int n, std::vectorlong long memo) { // 路线 A记忆化 if (n 1) return n; if (memo[n] ! -1) return memo[n]; return memo[n] fib(n - 1, memo) fib(n - 2, memo); }判断是否该加记忆化的方法画出递归树如果发现同一参数组合出现了多次就必须记忆化。这一条也是回溯升级为动态规划dynamic programming的分界线。总结把这三个概念重新串一遍概念一句话定义关键动作典型问题递归用自调用表达更小规模的同类问题写对基准情形阶乘、树遍历、分治搜索在状态空间树上系统枚举选对 DFS / BFS连通性、最短路回溯搜索 撤销遍历所有方案做出选择 / 恢复现场成对写全排列、N 皇后、子集以及三条可以带走的经验递归的空间代价是递归深度。深度可能上万时要么改迭代要么把栈搬到堆上递归函数内绝不放大的局部数组。做出选择和撤销选择必须成对出现中间夹一次递归调用。这是回溯不出错的唯一可靠保证。搜索的性能全在剪枝和状态编码上。用数组把 O(n) 的判断降到 O(1)N 皇后的三个布尔数组用排序把不可能的后续提前break掉——同一个算法剪枝与否能差出好几个数量级。最后递归、搜索、回溯这三剑客之所以总是一起出现是因为它们共享同一个世界观把问题看成一棵树然后决定怎么走、走错了怎么办。想通这一点这三样就不再是需要分别记忆的三个知识点而是同一件事的三种说法。