前两天翻百炼OJ的提交记录看到2748这道全排列题挂在未通过列表里第一反应是有点丢人递归这东西我平时没少写怎么一到OJ上就翻车。仔细复盘之后才发现问题压根不在递归本身而是我对回溯状态的处理太粗糙加上输出格式也跟着凑热闹白白提交了几次错误的版本。这篇错题本Vol.2就把全排列这道题从思路、代码、踩坑到扩展一次说清楚同时把递归算法在OJ场景下的常见问题一并梳理掉。1. 错题复盘全排列这道题到底卡在哪了1.1 题面的核心意图与OJ环境百炼OJ的2748题题目描述通常很短给定一个不含重复数字的数组返回它的所有全排列。像这类题目数据量一般在n≤9左右因为全排列总数是n!n10时已经有3628800个排列输出本身就够呛。题目真正考的是两件事第一你是否理解递归和回溯的状态变化第二你是否能在限定时间内按指定格式输出结果。很多同学看到全排列三个字就直接联想到C的next_permutation想着先sort再循环调用就完事。这种做法在本地调试没问题但放在OJ上经常会被判定为应对考试可以理解算法不行——不是说不能用而是这道题如果出现在数据结构或算法课程的OJ练习里出题人默认你要手写递归。更关键的是next_permutation生成的是字典序排列而手写回溯如果交换顺序没控制好输出顺序可能不符合题目要求的字典序这一点我在后面专门展开。1.2 我第一次提交为什么错了我的第一次提交用的是很常见的DFS标记法。代码逻辑上没错但我在退出递归时忘记恢复visited标志导致第一层选过的数字在后续分支里永远不能再次被选最终只输出了第一个位置的固定情况全排列直接缩水成n个排列。void dfs(int depth) { if (depth n) { // 输出 return; } for (int i 0; i n; i) { if (vis[i]) continue; vis[i] true; path[depth] a[i]; dfs(depth 1); // 这里漏了 vis[i] false; } }这种错误在纸上推演的时候很难发现因为人脑会自动补齐状态还原。但在OJ上少了这一行意味着每个数字一旦被选择整个递归路径就把它钉死了分支数量直接从n!降到n。回头想这就是对回溯二字理解不到位——回溯的本质是尝试之后把状态改回去而不是选择之后一路走到黑。这个错误被我记录在Vol.1里但Vol.2之所以还要写全排列是因为它还有更隐蔽的坑。2. 递归解全排列的正确打开方式从状态树到回溯框架2.1 把全排列看成一颗选择树要搞懂全排列的递归写法我建议你先别急着写代码而是画一颗状态树。以数组[1,2,3]为例第一位可以选择1、2、3分别得到三种分支第二位只能从剩下两个数字里选第三位只能选剩下的那一个。这颗树的叶子节点一共有3!6个对应六种排列。递归函数本质上就是在遍历这棵树。每次往下走一层就是在当前已经选了一些数字的状态下继续尝试所有还没被选过的数字每走到叶子节点就记录一个完整排列然后返回上一层撤销刚才的选择尝试另一个数字。这里有个关键点全排列的递归深度等于数组长度不是无限递归。很多新手担心递归层数太深会爆栈其实n≤9的题目递归深度最多9层完全不用担心。真正需要担心的不是深度而是分支数量呈阶乘增长。2.2 标记法用visited控制状态回退最直观的写法是用一个布尔数组visited记录某个下标是否已经被使用。每次递归时遍历所有下标选中未使用的加入路径递归然后撤销。#include iostream #include vector using namespace std; vectorint a; vectorint path; vectorbool vis; int n; void dfs() { if (path.size() n) { for (int i 0; i n; i) { if (i 0) cout ; cout path[i]; } cout endl; return; } for (int i 0; i n; i) { if (vis[i]) continue; vis[i] true; path.push_back(a[i]); dfs(); path.pop_back(); vis[i] false; } }这个框架有三个核心部分终止条件path.size() n说明已经凑齐了一个排列。选择列表for循环遍历所有数字通过vis过滤掉已选过的。撤销操作pop_back()和vis[i] false这是递归返回后必须做的否则状态污染。标记法的好处是直觉清晰对新手非常友好。缺点是visited数组每次都要遍历全部n个下标即使已经选了一大半。但既然n很小这不算问题。2.3 交换法空间更省的另一种思路等标记法写熟练之后我建议你再看交换法——这是很多教科书里推荐的写法也是百炼OJ这类平台常见的标准答案之一。交换法的核心思想是把选择第pos个位置放哪个数字看成在数组的pos到n-1范围内选一个数字交换到pos位置。递归深度到n时数组本身就是一种排列直接记录即可。void dfsSwap(int pos) { if (pos n) { for (int i 0; i n; i) { if (i 0) cout ; cout a[i]; } cout endl; return; } for (int i pos; i n; i) { swap(a[pos], a[i]); dfsSwap(pos 1); swap(a[pos], a[i]); } }交换法省掉了visited数组和path数组空间上更紧凑递归深度同样是n。但交换法有个隐患它生成的排列顺序不是严格字典序。如果你直接按[1,2,3]跑一遍输出是123、132、213、231、321、312这种顺序而标记法配合for循环从左到右遍历输出是123、132、213、231、312、321。两种顺序略有差别。如果题目要求字典序输出标记法天然满足交换法需要额外处理比如在for循环里先对候选数字排序或者最后对结果排序。所以我的建议是考试和刷题优先用标记法因为它的输出顺序可控思路也更容易讲解。写法额外空间输出顺序去重扩展难度推荐场景标记法visitedpath字典序容易OJ刷题/初学交换法几乎无非字典序较麻烦理解交换思想/空间受限3. 提交OJ时我踩过的三类坑3.1 输出格式OJ对排版的强迫症这道题在百炼OJ上的输出要求一般是每个排列占一行数字之间用一个空格隔开行末不能有多余空格。听起来很简单但我第一次提交就是这样被卡掉的。我那时候习惯用for循环直接输出for (int i 0; i n; i) { cout a[i] ; } cout endl;本地跑没有任何问题因为肉眼看不出末尾多了一个空格。但OJ是逐字符比对的末尾多空格直接判Presentation Error有时候甚至会判Wrong Answer。这个问题在递归输出多个排列时更容易被忽略因为你会把注意力放在排列本身是否完整而不是字符格式。正解是判断是否为当前行的最后一个数字for (int i 0; i n; i) { if (i 0) cout ; cout path[i]; } cout endl;我后来养成了一个习惯所有OJ输出题只要要求空格分隔一律用这种先判断后输出的方式不要嫌麻烦。另外还要注意换行有的题要求排列之间没有空行有的要求每行末尾有一个换行这些细节以题目原文为准。3.2 重复元素的排列去重问题2748这道题可能明确写了不含重复数字但我当时顺手用同样模板去刷另一道含重复数字的排列题结果一上来就输出了一堆重复排列。比如[1,1,2]的全排列如果不去重会输出[1,1,2]两次甚至三次。去重的标准做法是先把原数组排序然后在递归的for循环里如果当前数字和前一个数字相同并且前一个数字没有被使用过就跳过。sort(a.begin(), a.end()); for (int i 0; i n; i) { if (vis[i]) continue; // 去重核心如果当前元素和前一个元素相等且前一个元素未被使用 if (i 0 a[i] a[i - 1] !vis[i - 1]) continue; vis[i] true; path.push_back(a[i]); dfs(); path.pop_back(); vis[i] false; }这里有个容易混淆的点为什么是!vis[i-1]而不是vis[i-1]网上很多代码两种写法都有但含义不同。!vis[i-1]的意思是前一个相同的数字没被选中说明当前这个分支在前面的递归里已经被尝试过了跳过vis[i-1]是前一个已被选中说明当前是正常沿着前一个数字走下来的不需要跳过。我在实际测试中发现两种写法在有的情况下都能通过但!vis[i-1]是更稳的通用写法尤其是配合排序后使用。这个判断我建议直接背下来理解它的前提是你已经搞懂了回溯的时序。3.3 递归退出的边界n1和n0另一个容易忽略的边界是n1的情况。当数组只有一个元素时递归一旦进入就立刻满足终止条件直接输出该元素。这本身没问题但如果你在写终止条件时用了if (depth n - 1)这种写法就会导致n1时少输出一次甚至输出未初始化的数据。我在调试时遇到过n1输出正常但多了一个空行的情况最后发现是初始化path数组时多分配了一位导致输出时多了一个endl。这类边界问题在OJ上表现得很隐蔽小数据可能恰好通过大数据或特殊输入就崩。我建议在本地测试时每次写完整数输入后先跑一遍n1、n2、n0如果题目允许n≥1也要考虑n1的最小边界别只盯着样例数据测。样例通过不代表边界通过OJ判题就是处处设防。4. 复杂度与数据规模阶乘增长不是不讲道理4.1 时间都花在哪里全排列的递归时间复杂度是O(n!)这个大家都会说但很多人并没有真正感受过它的增长速度。我用一组数据来直观说明n5时全排列120个n8时40320个n10时3628800个n12时479001600个。也就是说每增加一个数时间消耗可能翻n倍。OJ上这类题通常会把n限制得很小比如n≤8因为输出量本身就已经很大了。有一次我拿n10的数据在本地跑测试程序跑了快两秒才把所有排列输出完其中大部分时间其实花在cout的IO上而不是递归本身。这说明一个经验如果遇到输出量特别大的OJ题输出部分可能是性能瓶颈。你可以尝试用printf替代cout取消同步后差距没那么大或者用puts直接输出字符串。我在刷题时习惯在开头加一句ios::sync_with_stdio(false);能明显加快cin和cout的速度但是如果输出量巨大还是printf更稳。4.2 空间开销与剪枝优化递归的空间复杂度主要看递归深度全排列的深度是n所以调用栈空间是O(n)。标记法额外需要一个visited数组O(n)和路径数组O(n)总体也是O(n)。这个空间开销在n≤9的题目里几乎可以忽略但要理解它因为后面做组合、子集问题时空间开销会随递归状态累积。剪枝优化在全排列里能做的不多因为你要的是全部排列任何一个分支都不能省略。但如果题目变成了输出满足某些条件的排列比如数字不能连续递增相邻两个数之和是质数就要在递归过程中提前判断不满足条件的分支直接跳过这种剪枝往往能把近似n!的复杂度降到可以接受的范围。我之前刷过一道排列中相邻数和为质数的题n9时如果不剪枝9!362880个排列全部枚举虽然也不算大但每次都要在叶子节点重新检查相邻和累计检查量很大。改成在for循环里检查path最后一个数和当前候选数的和是否为质数后虽然最坏情况仍然要遍历大量分支但实际运行时间下降了接近一半。4.3 用next_permutation可行吗这个话题我在第一节提过这里展开说。next_permutation是C标准库算法使用前提是当前序列已经是前一个排列且序列有序时从最小排列开始。用法很简单sort(a.begin(), a.end()); do { // 输出 a } while (next_permutation(a.begin(), a.end()));它能稳定输出字典序的全排列代码量极少而且速度通常比手写递归快。但问题在于第一它需要先排序如果题目输入本身无序你要么排序丢失原顺序要么先记录原顺序再额外处理第二很多OJ课程题明确要求使用递归实现你用STL是通过不了的会被判定为不符合题意。我的态度是刷题练习阶段递归必须手写一遍STL可以拿来验证输出结果是否一致。比赛或工程里则直接用STL因为没人会拒绝标准库。错题本的意义就在于把会用和理解分开这篇Vol.2本身就是帮我把递归理解得更深。5. 从全排列延伸一套回溯模板覆盖组合子集5.1 组合问题的相似模板全排列递归的核心框架一旦掌握组合类问题几乎是同一套模板的小改动。比如从n个数中选k个数的组合区别只有两个递归终止条件从path.size() n变成了path.size() kfor循环的起始位置不是从0开始而是从start开始以避免选中之前的元素造成顺序重复。void dfsCombine(int start) { if (path.size() k) { // 输出组合 return; } for (int i start; i n; i) { path.push_back(a[i]); dfsCombine(i 1); path.pop_back(); } }用start而不是visited数组来保证后续只能选更大的下标是组合问题比排列问题更快的关键。因为组合不看顺序[1,2]和[2,1]是同一种如果也像排列一样每次从0开始选会产生大量重复且白白增加计算量。我在做东方博宜OJ和郑州轻工业大学OJ的题目时发现很多看似不同的回溯题底层框架都一样。把全排列这一道彻底搞懂组合、子集、棋盘类问题都能触类旁通。当然不同平台名称不在讨论范围内我只是想说这类题的共性很强。5.2 子集问题与全排列的对照子集问题其实比排列更简单每个元素有选和不选两种状态递归可以在任意节点收集结果而不是只收集叶子节点。如果套用全排列的写法很多人会卡在为什么子集输出会重复上原因就是没有用start控制选择范围。void dfsSubset(int start) { // 每次进入都记录当前path for (int i start; i n; i) { path.push_back(a[i]); dfsSubset(i 1); path.pop_back(); } }这个写法最让人迷惑的地方是它没有显式的终止条件靠的是for循环自然结束。看起来不像递归但它确实在遍历一颗子集树。理解它之后你会对递归的终止可以是循环条件结束有更深的认识。5.3 带限制的排列进阶思路回到排列本身进阶题型一般是在选择时增加约束。比如给定数字集合求所有排列中满足奇数位不能放偶数的排列或者相邻数字之差的绝对值大于m的排列。这类题不需要改变回溯模板只需要在for循环里在vis[i] true之前增加剪枝判断。判断不通过就直接continue等于把这颗子树整棵剪掉。这个动作看起来简单但能体现你对递归搜索树的理解程度剪枝的位置决定了效率剪枝的条件决定了正确性。我刷过的最典型的一道是这个给出1到n的数字要求所有排列中任意相邻两个数的和都是质数。n9时全排列36万个加上剪枝后实际枚举量少了很多。而且这类题对输出顺序也有要求用标记法天然符合字典序用交换法还得排序这再次验证了标记法在OJ练习中的通用性。回到2748这道题我在错题本上写下的总结只有三句话递归结束必须还原状态输出格式严格按题目要求重复元素先排序再剪枝。这三句话看着简单但每一个背后都是一整段踩坑经历。如果你也在刷全排列相关的OJ题把这三点先刻在脑子里能省下不少提交次数。