最近在百炼OJ刷题一道编号2748的全排列把我虐得够呛。递归算法写到第三版才通过前两版不是重复输出就是少了组合wa到怀疑人生。回头复盘其实全排列是递归算法入门里最典型的题但越是经典越容易在细节上翻车。这篇错题本Vol.2我把自己从”背模板“到”真正理解递归回溯“的整个过程都整理出来包括递归函数怎么设计、调用过程怎么展开、回溯时状态为什么必须恢复以及提交时容易踩的各种格式和逻辑坑。如果你也正在啃递归算法或者被这类”输出所有方案“的题目折磨过这篇文章应该能帮你省下不少试错时间。2. 题目拆解全排列到底考什么2.1 题面分析与数据范围判断百炼OJ的这道全排列题题面很简洁输入一个正整数n要求按字典序输出1到n的所有全排列每个排列占一行数字之间用空格分隔。比如n3时输出1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1第一眼觉得简单就是想个办法把n个数字的所有排列都打印出来。但真正写的时候才会发现这里的难点不只是“列出所有方案”还有两个隐藏要求一是字典序输出二是格式严格行末不能多空格每个排列必须换行。来算一下数据范围。n个不同元素的全排列数量是n!也就是1×2×3×…×n。如果n1010! 3628800也就是要输出三百多万行如果n1212! ≈ 479001600接近五亿行光输出就得卡死。所以这类题目的n一般在8到10左右最多到12。拿到题目先算这个你就能大概预判自己的算法会不会超时也能理解为什么OJ通常把数据控制在合理范围内。2.2 全排列与递归模型的对应理解全排列可以从“做决策”的角度切入。把排列过程想象成往n个位置里填数字第一个位置可以从n个数字里选一个第二个位置只能从剩下的n-1个里选第三个位置从剩下n-2个里选……直到所有位置填满。每一步的选择范围取决于之前已经选了多少个数字。这个模型和递归天然对应位置下标cur表示当前在处理第几个位置递归深度就是cur的值从0到n-1当cur等于n时说明所有位置都填满了输出当前方案。每一层递归要做的事情高度一致——“枚举当前还能选的每一个数字选完进入下一层”。这种“重复地做同一件事只是状态不同”的结构正是递归能解决的典型场景。2.3 为什么一看就懂、一写就废我见过很多同学包括我自己在草稿纸上画递归树头头是道一上机写代码就各种错。核心原因是“看到的正确代码”和“脑袋里能画出来的调用过程”之间有断层。代码里的一行dfs(cur 1)背后其实是一棵庞大的递归调用树树的每个节点都是一个完全独立的“现场”。如果没有在“代码逐行执行”和“函数调用栈”之间建立对应就很容易出现两种情况要么不知道怎么处理“已选数字”把同一个数字重复选要么在递归返回后忘了撤销导致后面的分支拿到错误状态。说白了全排列考察的从来不只是“你会不会排列”而是你有没有真正理解递归调用的“进入-返回-状态恢复”这一整套机制。这也是我把它写进错题本的原因。3. 递归算法的核心三步法与递归树3.1 递归函数三要素怎么定写递归函数之前先把这三件事想清楚第一函数参数设计。全排列里需要知道“当前要做到第几个位置”所以至少要有一个cur参数还需要知道“哪些数字已经选过”所以需要一个used[]标记数组以及一路累积下来的排列内容一般用一个path数组或vector来存。这三样东西就是递归函数手里的全部“现场”。第二终止条件。当cur n时所有位置都填完了这是递归的出口在这里输出path并return不能再继续往下递归。第三递归转移。枚举当前可选的所有数字选一个放进path标记used然后调用dfs(cur 1)进入下一层。注意这还没完——从下一次调用返回后必须把刚才的“选择”恢复原状也就是把used标记清掉、把path最后一个元素弹出去让同一层循环的下一次迭代能拿到一个干净的状态。3.2 从递归树看调用过程拿n3举例。dfs(0)进入后第一层循环i从1到3先选1path [1]进入dfs(1)。dfs(1)里不能选1了只能选2或3。选2path [1,2]进入dfs(2)此时只剩3填进去输出1 2 3返回回到dfs(1)撤销2再选3path [1,3]进入dfs(2)填2输出1 3 2返回。dfs(1)处理完所有分支后返回dfs(0)撤销1然后第一层循环i2选2重复上一轮逻辑。展开来看递归树第一层有3个节点每个节点下面又有2个分支叶子层就是6个完整排列。你会看到整棵树的结构是逐层分叉、依次收缩的——第一层分支数是n第二层是n-1第三层是n-2。这个树形结构就是全排列的所有可能方案递归的作用就是把这棵树完整地遍历一遍。3.3 回溯的本质状态恢复我在初学阶段一直不理解为什么递归返回后要把used[i]改回false这个问题的答案恰恰是全排列算法里最重要的部分。想象你要从楼梯上到三楼每上一层就记一笔走到三楼看到风景后你得一层一层退下来每下一层就要把楼层记录擦掉。如果你不擦掉退回到二楼时记录里仍然写着“三楼”你再走另一条楼梯上三楼会发现记录里还残留着之前楼层的信息导致判断错误。递归里的used标记就是楼层记录path里存的就是你走过的路径。递归返回本质上是“回退到上一层调用栈”而调用栈里的局部变量确实会自动恢复但used和path是递归层之间共享的状态要么是全局变量要么是引用传参它们不会自动恢复必须手动撤销。很多新手写全排列死循环或者输出大量错误方案根子都在这里只做了“选”和“递归”忘了“撤销”。4. 完整代码实现与逐段拆解4.1 一张可直接提交的DFS模板先把代码完整贴出来我用的是C百炼OJ完全兼容提交时直接选C语言即可。#include cstdio #include vector using namespace std; vectorint path; int n; bool used[15]; void dfs(int cur) { if (cur n) { for (int i 0; i n; i) { printf(%d%c, path[i], i n - 1 ? \n : ); } return; } for (int i 1; i n; i) { if (!used[i]) { used[i] true; path.push_back(i); dfs(cur 1); path.pop_back(); used[i] false; } } } int main() { scanf(%d, n); path.reserve(n); dfs(0); return 0; }这份代码很短但每一行都有讲究。下面我按执行顺序拆开说。4.2 为什么需要visited标记数组used[15]是全局数组初始全为false。它的作用是记录数字i是否已经在当前排列里。每次选择数字i前都检查if (!used[i])保证同一排列中不会重复选同一个数字。这里有个细节值得新手注意为什么用used数组而不是“在path里找”因为全排列的n最多也就10左右在path里find一遍其实也很快但used数组做到了O(1)判断而且代码更直观。更重要的是用used标记才能配合“撤销”这个动作——选中时置true递归返回后置false这样不同分支之间才能互不干扰。4.3 输出格式与字典序问题先说输出。代码里用了printf(%d%c, path[i], i n - 1 ? \n : )这是每个数字后跟一个空格最后一个数字后跟换行。如果你直接在每个数字后面打印空格最后一会多出一个空格OJ对多余的空格非常敏感经常因为这个wa。我在第一次提交时就踩了这个坑现在每次都习惯性地用这种“最后一位特殊处理”的写法。再说字典序。题目要求按字典序输出。字典序本身是第一位的数字小的排在前面第一位相同再比较第二位。我们按for (int i 1; i n; i)的顺序从小到大枚举以此产生的排列天然就是字典序。如果你改成从n到1倒着枚举输出就会变成逆字典序也会wa。这里不需要额外处理只要枚举顺序对就行。4.4 为什么不建议用cout和递归返回后的恢复写法有同学习惯用cout输出不是不行但这类输出量巨大的题目printf比cout快不少而且printf可以顺带控制空格和换行不容易出格式问题。我一般直接写printf习惯之后并不觉得难用。至于“撤销”这两行代码的位置path.pop_back(); used[i] false;它们必须紧跟在dfs(cur 1)之后不能颠倒也不能漏。先弹出一个数字再把对应的used标记清空顺序反了也问题不大因为一个修改path一个修改used互不影响但漏掉任何一个都会让后续枚举被“残留状态”污染。我直接在脑子里把“选择-递归-撤销”当成一个固定节奏每次写完都检查一遍三行是否齐全。5. 常见错误与排查技巧实录5.1 错误对照表我把刷这道题过程中遇到、以及帮同学排查时见过的典型错误整理成了一个表方便大家直接对照错误现象根本原因解决思路输出中同一排列反复出现递归返回后未重置used检查used[i] false是否遗漏只输出部分排列缺方案终止条件或枚举范围写错检查cur n检查循环边界输出里出现重复数字没用used标记或标记逻辑错误选数字前必须判断!used[i]每个排列末尾多一个空格输出时对所有数字都打印空格最后一个数字单独处理为换行本地结果对OJ报WA字典序要求未满足确认枚举循环从小到大提交超时TLEn较大时递归方案数太多检查n范围必要时优化输出缓冲5.2 排查递归错误的核心方法人肉栈模拟在我看来排查这类问题最有效的方法就是“人肉栈模拟”。用n3这样的小数据把递归树的执行过程在纸上手动走一遍同时对照代码拍每一行。哪个节点的状态不对立刻就能定位。我之前犯过的一个典型错误是把used[i] true写在if外面导致所有分支都认为i被用过最终第一层只能选一个数字整个递归树直接断掉。这种错不跑一遍纸面模拟很难发现因为你只看代码逻辑会觉得“只是位置放错了”。所以这里要特别强调used[i] true和path.push_back(i)必须放在if (!used[i])的代码块内部。5.3 用局部全局变量和引用传参的坑另一个常见的坑是函数传参。有些同学喜欢写void dfs(int cur, vectorint path, vectorbool used)这样每次递归都会复制一份path和used逻辑上确实正确也不会出现“忘了撤销”的问题因为每层都有自己的拷贝。但代价很大n10时每个节点复制两个数组递归树有几百万个节点时间和内存都会爆掉。但反过来说如果一定想用值传递省掉撤销逻辑那就要接受性能损失。我的建议是用全局变量配合push_back和pop_back手动维护状态这是最标准、最省资源、也最贴合OJ场景的写法。理解了手动撤销的原因你才算把一个递归算法的“状态管理”真正想明白了。6. 从全排列到排列组合的扩展6.1 有重复数字时的去重方案上面讨论的是数字互不相同的标准全排列。如果题目改成“给定一个可能含重复数字的数组输出所有不重复的全排列”算法要怎么做这时不能简单地用上面的模板否则重复数字会生成大量重复排列。比如[1,1,2]直接枚举就会输出两组1 1 2。处理去重的标准做法两步走先把数组排序让相同的数字相邻然后在递归枚举时如果发现当前数字和前一个数字相同且前一个数字还没有被使用!used[i-1]就跳过当前这个分支。理解这个规则的关键在于相同数字的所有排列本质上相同只要在这层枚举中选第一个就行了后面重复的不用重选。这个剪枝逻辑在全排列的升级题里几乎是必考的。6.2 排列和组合的递归写法为什么不一样正好在这里区分一下排列和组合两者很容易混淆。全排列关注“顺序”每一个排列里数字出现的顺序不同就代表不同方案所以需要used数组来避免重复选择每个位置可选的数字都是当前还没用过的所有数字。组合问题比如从n个数字里选k个不关心顺序所以不需要used数组而是在递归的时候传上一个start下标从此只能选后续位置的数字避免出现[1,2]和[2,1]被当成两种方案的重复计数。我在初学时很长一段时间内排列组合分不清后来悟了一句话排列靠used控制“哪些能用”组合靠start控制“还能从哪开始”。记住这句话遇到多数题都能快速判断该用哪种模板。6.3 这道题的复杂度与后续刷题方向全排列的递归树叶子数量是n!整棵树的节点数大概是叶子数的e倍左右所以时间和空间复杂度都是O(n!)。这样的增长曲线极其陡峭n稍微大一点就无能为力这也是为什么OJ只会给很小的n。如果面试或竞赛中遇到n比较大的排列类问题一般要考虑公式计算、数学剪枝或者换用其他算法而不是硬枚举。刷完全排列可以继续刷这些递归延伸题组合总和、子集、八皇后、括号生成。它们的递归套路都一样只是状态和剪枝条件不同。做这一系列题的时候每次遇到“输出所有方案”的题我都会下意识地问自己这题用used还是start递归终止条件在哪返回后状态恢复没这三个问题问完递归题的大框架就立住了。我在实际写全排列的时候最深的体会是递归算法真的不是靠背模板而是靠一遍遍画递归树、人肉模拟、在遗忘撤销时被现实毒打——然后彻底明白“状态恢复”这四个字的分量。如果这篇文章能让你少踩一次撤销状态的坑那这个错题本Vol.2就没白写。后续我会继续更新其他递归算法的错题实录。