企业官网建设流程全解析

递归算法刷题最容易出现的情况，就是“代码写完感觉天衣无缝，一提交不是超时就是乱序，偶尔还直接死循环”。这篇错题本Vol.2记录的是百炼OJ（POJ）的2748题：全排列。这道题是递归和回溯算法的经典入门题，也是很多学校机试、公司笔试喜欢拿来摸底的基础题，题目本身不难，但它把“递归状态恢复”“搜索顺序与字典序的关系”“输出格式控制”这几个关键点全部揉在了一起，非常适合用来做阶段性的递归能力自查。

先说结论：如果你正在学递归、准备算法竞赛入门，或者马上要参加机试面试，这道题值得认认真真手写一遍，而不是直接调STL的next_permutation糊弄过去。手写全排列能让你彻底理解“决策树展开”和“回溯撤销”这两个递归核心动作。文章会基于我在百炼OJ上实际提交、踩坑、改错的经验，把题目分析、递归思路、完整代码、常见提交错误全部拆开来讲，最后还会整理一份速查表，方便你下次遇到同类题直接对照。

1. 题目回顾与递归思路的形成

1.1 先搞清楚题目到底在问什么

POJ 2748的题面非常简洁：输入一个正整数n（一般限制在1到9之间），要求输出1到n这n个数字的所有全排列，每个排列占一行，数字之间用空格分隔，并且所有排列要按字典序从小到大输出。

这里的“字典序”是关键约束。拿n=3举例，输出顺序必须是：

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

不能是乱序输出，更不能漏掉任何一个排列。n=3的时候一共只有6个排列，手算都能列出来，但一旦n到了8、9，排列总数会膨胀到40320和362880，这时候就必须靠程序系统地生成，而“系统”这两个字，天然就是递归的强项。

顺带说一句，n被限制在9以内是有道理的。n=9时全排列总数是9! = 362880个，每个排列包含9个数字，光输出就是300多万字符，已经不算少了。n=10的话排列数直接到3628800，除非题目有特殊要求，否则一般的OJ时间限制会很紧张。所以看到n<=9这个范围，基本可以断定出题人就是想让选手用递归回溯法来解，而不是搞什么高端优化。

1.2 用“填盒子”模型理解递归展开

全排列的递归过程，我习惯把它理解成“依次往n个空盒子里放数字”。第一个盒子可以放1到n中任意一个数字，有n种选择；第二个盒子只能放剩下未被使用的数字，有n-1种选择；以此类推，到最后一个盒子时只剩下1种选择。

把每个“选择”看作树的一个分叉，整个搜索过程就是一棵深度为n的决策树。从根节点到任意一个叶子节点的路径，恰好对应一个长度为n的排列，而叶子节点的总数就是n!。递归函数写起来其实就是这棵树的深度优先遍历：每往下走一层，就决定一个盒子里放什么数字；走到底（填满n个盒子）时输出当前排列，然后回退到上一层，尝试另一种选择。

用生活化一点的话说，这就像你出门前挑衣服：上衣先试衬衫，试完记下来，再试T恤；配的裤子同理，每换一件上衣，裤子都要从第一条重新开始配。等所有组合都试过一遍，就是一次完整的“全排列遍历”。

1.3 为什么这题最适合检验递归基础

很多题目能用递归解，但也能用迭代、位运算甚至数学公式解，选哪个都行。全排列不一样的地方在于，它几乎是“为递归量身定做”的：

第一，递归的每层调用对应“决策树的一层”，概念映射非常自然，不存在牵强的感觉。第二，它强制要求你在递归返回后做“状态恢复”，也就是把之前标记为“已使用”的数字重新标记为“未使用”，这一步不做，整个程序就会输出一大堆重复或残缺的排列。第三，它还顺带考察了字典序控制，虽然不复杂，但需要你理解搜索顺序和输出顺序的关系。

我在刷题群里见过很多同学，看题解觉得“这有什么难的”，闭眼也能默写模板，但一改条件就懵。比如把“1到n的全排列”改成“给定一个可能含重复数字的数组，输出所有不重复的全排列”，立刻有一半人翻车。根源就是没有真正理解递归的状态变化过程，只记住了表面写法。所以这篇错题本选择全排列作为主题，就是想借这道题把“递归+回溯”的内功练扎实，后面再遇到组合求和、子集枚举、N皇后、数独等回溯经典题，你才能举一反三。

2. 核心细节：递归函数设计与回溯的关键动作

2.1 递归函数参数怎么设计才不容易乱

写递归函数，第一件事是确定“当前进度”用什么表示。全排列里，最直观的进度就是“已经决定好了前几个位置”，我常用的参数名是step或者depth，表示下一步要填第几个盒子。

除了进度参数，递归过程还要知道“哪些数字已经用过了”，以及“当前已经排列好的数字有哪些”。这里有两种主流方案：

方案一：使用一个bool used[n+1]数组标记每个数字是否被使用，再用一个int path[n]数组按顺序存放已经选好的数字。这是最经典、也最容易讲清楚的写法。

方案二：直接在待选列表中用交换法操作序列本身，不额外开used数组。这种写法代码更短，但理解门槛稍高，而且字典序处理不如方案一直观，新手不建议从这种写法入手。

我强烈建议初学者先吃透方案一。used数组是“状态”，path数组是“结果路径”，两者职责清晰，调试的时候打印出来也容易定位问题。等你对回溯已经形成肌肉记忆，再去尝试方案二也不迟。

2.2 路径记录与递归终止条件的配合

路径记录有一个很容易被忽视的点：path数组下标和depth参数必须严格对齐。depth=0表示一个数字还没选，path[0]是待填的第一个位置；depth=n表示n个位置全部填完，这时候就到了递归出口，应该输出结果并返回。

递归出口写错是常见的隐形Bug。比如把出口写成if (depth == n - 1)，那最后一位数字还没填进去就输出，得到的全是n-1长度的“残缺排列”，而且每个排列之间还会互相污染。这种错误在本地跑小数据时很容易看出来，但在某些自定义测试数据下可能恰好不报错，等提交到OJ才发现连样例都过不了。

路径数组输出的时候还有一个细节：数字之间的空格分隔。很多人习惯在循环里每个数字后面都打一个空格，这样做样例能过，但OJ的判题系统（尤其是POJ这类严格模式）会报Presentation Error，也就是“格式错误”。正确做法是：第一个数字前不打空格，之后的每个数字前打一个空格，行末统一换行。代码写起来就是先判断下标是否大于0，大于0就先输出一个空格，再输出当前数字。

2.3 递归返回后的“撤销选择”为什么不能省

这是整个递归回溯里最重要的一步，也是我当年第一次提交全排列时翻车的地方。

在每一层递归里，选择一个数字后，我们会把它标记为used[i] = true，然后继续递归下去。递归返回时，必须立刻把它恢复成used[i] = false，同时把路径数组里的对应位置“清空”（实际写代码通常是直接覆盖，不需要真的删除）。

为什么必须恢复？因为used数组是全局共享的状态，不是某一条递归分支私有的。想象你在迷宫里走，做标记用的绳子如果不随身带走，下一趟探索就会被上一趟的标记误导。如果递归访问完数字1分支的所有排列后，used[1]仍然是true，那么后面所有尝试2、3开头排列的分支，都会错误地认为数字1已经不可用，最终导致大量排列缺失，甚至整个程序输出为空。

这时候再回头看“回溯”这个词：递归向下走是“递”的过程，递归返回后恢复状态是“归”的过程。先进入、再退出，退出时把现场还原成进入之前的样子，这才是完整的回溯。只递不归，就是有去无回的死胡同。

2.4 字典序是怎么被保证的

很多第一次做这题的人都会困惑：代码里也没写任何排序，为什么输出天然就是字典序？

秘密在搜索顺序。只要在每一层递归里，从小到大依次尝试“当前尚未使用的数字”，那么第一层先固定1开头的所有排列，再固定2开头的所有排列……由于每一层的选择都是升序的，最终生成的排列序列自然满足字典序。

以n=3为例：

• 第一层尝试1，进入递归后，第二层尝试2，第三层尝试3，得到排列1 2 3；
• 第三层尝试完回到第二层，第二层再尝试3，第三层尝试2，得到排列1 3 2；
• 第二层全部试完回到第一层，第一层尝试2……

整个过程就是深度优先搜索的自然产物。所以写循环的时候，for (int i = 1; i <= n; i++)这句不要乱改起点和终点，一旦改成从n倒着遍历，所有排列顺序就会整个反转，字典序直接破坏。如果哪一天题目要求“逆字典序输出”，那才需要考虑调整循环方向，这是后话。

3. 完整代码实现与逐行解读

3.1 C++递归回溯标准写法

下面这段是我在百炼OJ上验证过的版本，也是我推荐给初学者的模板。写法上做了清晰的职责划分：dfs负责搜索，printPermutation负责格式统一的输出。

#include <iostream> #include <vector> using namespace std; int n; vector<int> path; vector<bool> used; void printPermutation() { for (int i = 0; i < n; i++) { if (i > 0) cout << ' '; cout << path[i]; } cout << '\n'; } void dfs(int depth) { if (depth == n) { printPermutation(); return; } for (int i = 1; i <= n; i++) { if (!used[i]) { used[i] = true; path.push_back(i); dfs(depth + 1); path.pop_back(); used[i] = false; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); while (cin >> n) { path.clear(); used.assign(n + 1, false); dfs(0); cout << '\n'; } return 0; }

这里有几个细节值得展开说。

第一，ios::sync_with_stdio(false)和cin.tie(nullptr)这两行是我刷OJ的习惯性动作。全排列在n=9时输出量超过三百万字符，如果不去掉C和C++输入输出流的同步，频繁刷新缓冲会让运行时间明显变长。在POJ这类对时间要求严格的题目上，这种IO优化往往是“超时”和“稳过”之间的分水岭。平时自己练习未必感觉得到，但养成习惯没坏处。

第二，used.assign(n + 1, false)保证了每次处理新的n时，状态数组都是干净的全false。下标从1到n对应数字本身，下标0虽然浪费了，但换来了代码可读性，不亏。如果你追求极致空间，可以用used(n + 1)初始化后配合fill重置，但没必要。

第三，输出函数单独封装有两个好处：一是dfs里不需要在循环中手写复杂的输出逻辑，二是一旦发现格式错误，只需要改printPermutation一个地方，不用在所有递归调用点里翻找。这个习惯在更复杂的题目里能省你大量调试时间。

3.2 复杂度分析与极限规模下的表现

很多人只关心“能不能过”，不太算复杂度，这其实是刷题的大忌。全排列的时间复杂度可以从决策树的角度来推：

• 第一层有n个分支；
• 第二层每个分支又有n-1个子分支；
• 第三层继续递减；
• 整个树的总叶子数是n!，每个叶子对应一次完整的输出，而输出本身需要遍历长度为n的路径，复杂度是O(n)；
• 内部的非叶子节点也各自需要O(1)的循环判断，相对于叶子节点的操作量可以忽略不计。

所以整体时间复杂度是O(n! × n)。n=9时大约是362880 × 9 ≈ 326万次基本操作，再算上输出字符的量级，现代OJ在一秒内跑完毫无压力。但如果你试图用全排列去处理n=12甚至更大，指数级爆发会让你瞬间明白为什么需要更高级的搜索剪枝算法。这也是为什么很多题目把n卡在8或9的原因——出题人就是想让你用回溯法，否则去重、子集、组合类问题根本没法做。

空间复杂度就简单了：path和used各自是O(n)，递归调用栈的深度等于决策树的高度也是O(n)，所以总空间复杂度是O(n)。这是典型的“时间换空间”型算法，内存占用小，但运行时间随输入规模爆炸增长。

3.3 用STL的next_permutation能不能偷懒

肯定有人会说，题目输出全排列，直接用next_permutation不香吗？代码更短，还不用担心递归写错。确实，C++标准库提供了这个函数，用起来很简单：

#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int n; while (cin >> n) { vector<int> nums(n); for (int i = 0; i < n; i++) nums[i] = i + 1; do { for (int i = 0; i < n; i++) { if (i > 0) cout << ' '; cout << nums[i]; } cout << '\n'; } while (next_permutation(nums.begin(), nums.end())); cout << '\n'; } return 0; }

这段代码在POJ 2748上也能AC，因为next_permutation本身就是按字典序生成下一个排列的，内部实现原理恰恰就是“从后往前找升序对、交换、反转后缀”这套经典流程。从实用角度，比赛里用STL完全没问题。

但作为练习题，我强烈建议至少完整手写一遍递归版。原因有两点：第一，next_permutation把核心算法全部封装了，你很难通过它理解“回溯状态恢复”这个思想，而这是面试里很常考的点；第二，实际工作中很多排列组合问题并不是“给定1到n”，而是“给定带重复元素的数组，输出不重复排列”，这时候next_permutation依然能用（它会自动跳过重复排列），但如果题目还要求你按某种自定义规则生成部分序列，手写递归和回溯几乎是唯一可靠的选择。工具要会用，原理更要懂。

4. 实战中的典型提交错误与排查实录

4.1 症状一：输出全是一个排列，或者排列明显变少

这个症状几乎是“忘记恢复状态”的标配。我当年第一次写全排列，dfs里只写了used[i] = true，递归返回后忘记写used[i] = false，结果n=3时只输出了“1 2 3”这一个排列，因为数字1在被标记为使用后，第二层就只能选2，第三层只能选3，一路走完所有递归层，程序直接结束，根本没有回到第一层尝试数字2的机会。

排查方法很简单：在dfs函数的入口和return之前各打印一行，观察递归的进入和退出顺序。如果发现某个数字被used标记后再也没有被释放，那问题基本就锁定了。

4.2 症状二：输出结果有重复排列

这个症状一般出现在你对“选择列表”没有正确约束的情况下。比如你没有用used数组，而是直接判断“当前数字是否已经出现在path里”，用循环扫描path来避免重复，但扫描范围写错了，或者递归返回后没有把path里最后一个元素弹出去，导致上一层误以为某些数字已经被用过，从而出现重复或缺失。

还有一种隐蔽情况：在同一个递归分支里同时对used数组和path数组做修改，但顺序不统一。比如在递归调用前先push_back，递归返回后又忘了pop_back，导致path的长度和depth不一致，输出时自然会出问题。正确顺序是：标记used、push、递归、pop、取消标记，这个顺序不要打乱。

4.3 症状三：运行超时

n在9以内，递归版很少超时，一旦超时，优先检查是不是输入输出拖了后腿。最常见的问题有两个：一是用了endl而不是'\n'，endl除了换行还会强制刷新输出缓冲区，在输出几十万行的情况下会造成巨大的性能浪费；二是没有关闭C和C++的IO同步，导致每次输入输出都有额外的同步开销。

另外，有些人会在递归函数内部用vector的find来检查数字是否已使用，比如find(path.begin(), path.end(), i) != path.end()，这个操作是O(n)的，在每一层递归里都要扫描整个path，虽然n很小看不出大问题，但整体复杂度会从O(n! × n)退化到O(n! × n²)，在极限数据下会明显变慢。正确的做法始终是用bool used数组做O(1)的判断。

4.4 症状四：提交报Presentation Error

Presentation Error（PE）是POJ这类OJ特有的错误，意思是答案本身没错，但输出格式有偏差。全排列最常见的PE原因就是行尾多了空格。

我见过有人这么写输出：

for (int i = 0; i < n; i++) { cout << path[i] << ' '; } cout << '\n';

这样做每个排列末尾都会多一个空格。在本地肉眼看不出来，因为显示效果一样，但判题系统是逐字符比较的，空格也是字符，于是直接PE。解决办法我在前面的代码里已经写了：输出前判断一下下标，i == 0时不打空格，否则先打空格再输出数字。

还有另外一种PE是输出完一组排列后多了一个空行。题目不同要求不同，POJ 2748的多组数据之间通常需要空行分隔，但最后一组之后不能有多余空行。我在代码里统一在每个n的输出结束后打一个'\n'，这在多数情况下是安全的，但严格来说最稳妥的写法是判断是否是最后一组。不过对2748这道题，样例和实际数据都没在这个细节上卡人，直接这样写也没问题。

4.5 错题本速查表

5. 从全排列延伸出去：去重与更复杂的回溯问题

5.1 如果输入数组含有重复数字怎么办

很多同学觉得会了“1到n全排列”，就觉得全排列问题通关了，结果在面试里遇到“给定数组[1,1,2]，输出所有不重复排列”直接卡住。这个变体是对“去重”的考察。

解法套路是先对数组排序，让重复元素相邻，然后在递归的每一层循环里加一个判断：如果当前数字和前一个数字相等，并且前一个数字在本层还没有被用过，就跳过当前数字。写成代码就是：

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { continue; }

这里的逻辑要仔细想一下：!used[i - 1]表示前一个相同数字在“当前这层”还没有被选择。因为我们是按排序后的顺序遍历的，所以在同一层里，一旦前一个相同数字已经在这一层被使用过，继续选后面的相同数字就会产生重复排列。而如果前一个相同数字已经被更深层的递归使用了（used[i - 1] == true），那说明当前这个数是作为不同位置上的数出现的，这种情况要保留。

这个判断是面试里常考的高频细节，很多人只背结论不推原理，改个条件就不会了。如果你能把“为什么是!used[i - 1]而不是used[i - 1]”讲清楚，面试官对你的递归理解基本就放心了。

5.2 递归深度与栈空间的现实问题

全排列这一题的递归深度等于n，n最多是9，所以栈空间完全不构成威胁。但很多人在写其他递归题时，会忽略递归深度这个隐藏风险。

系统栈的默认空间一般在8MB左右（不同OJ、不同环境有差异），每层递归的栈帧大小又与函数局部变量数量有关。如果递归深度达到几万层，程序会直接栈溢出崩溃，这时候你再优秀的算法逻辑都没用。解决思路通常是改用显式栈模拟递归，或者用尾递归优化（如果编译器支持的话），再或者改变算法改用迭代写法。全排列之所以能用递归轻松过题，正是因为n很小，递归深度可控，这也是出题人选择这个范围的原因之一。

5.3 这类递归题还能怎么变着法考

全排列是“组合爆炸”类问题的地基。理解了它，你就理解了回溯算法的通用模板：

void backtrack(当前路径, 可选列表) { if (满足终止条件) { 记录结果; return; } for (选择 in 可选列表) { 做选择; backtrack(更新后的路径, 更新后的可选列表); 撤销选择; } }

把“选择列表”从“1到n的数字”换成“数组下标”、把“路径长度n”换成“目标和为target”，就变成了子集求和问题；把“一维路径”换成“棋盘上的列坐标”，就变成了N皇后问题；把“任意排列”换成“候选数字可以无限次使用”，就变成了组合总和问题。

我个人的体会是，与其背十道题的题解，不如把全排列这一道题的递归过程在纸上完整走一遍，每一步画出当前path和used的状态，你会发现所有回溯题目都是在同一个模板里做文章。这也就是为什么我把这篇放在递归算法错题本的第二篇：上一道题还在讲分治，这一道题开始引入“带状态恢复的深度优先搜索”，后面再写N皇后、数独、图的拓扑排序时，我们就有了共同的语言基础。

最后再分享一个小技巧：刷这类递归题时，准备一个debug函数，在递归入口打印depth、path内容和used状态，通过观察输出变化来理解递归的进入和退出顺序。这个方法帮我省下了大量对着代码干瞪眼的时间。等你真正理解了递归的过程，调试打印自然就不需要了，因为你的心里已经能跑完整个决策树了。