递归算法错题本：手写全排列吃透回溯与字典序-北京尧图网络

递归算法刷题最容易出现的情况就是“代码写完感觉天衣无缝一提交不是超时就是乱序偶尔还直接死循环”。这篇错题本Vol.2记录的是百炼OJPOJ的2748题全排列。这道题是递归和回溯算法的经典入门题也是很多学校机试、公司笔试喜欢拿来摸底的基础题题目本身不难但它把“递归状态恢复”“搜索顺序与字典序的关系”“输出格式控制”这几个关键点全部揉在了一起非常适合用来做阶段性的递归能力自查。先说结论如果你正在学递归、准备算法竞赛入门或者马上要参加机试面试这道题值得认认真真手写一遍而不是直接调STL的next_permutation糊弄过去。手写全排列能让你彻底理解“决策树展开”和“回溯撤销”这两个递归核心动作。文章会基于我在百炼OJ上实际提交、踩坑、改错的经验把题目分析、递归思路、完整代码、常见提交错误全部拆开来讲最后还会整理一份速查表方便你下次遇到同类题直接对照。1. 题目回顾与递归思路的形成1.1 先搞清楚题目到底在问什么POJ 2748的题面非常简洁输入一个正整数n一般限制在1到9之间要求输出1到n这n个数字的所有全排列每个排列占一行数字之间用空格分隔并且所有排列要按字典序从小到大输出。这里的“字典序”是关键约束。拿n3举例输出顺序必须是1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1不能是乱序输出更不能漏掉任何一个排列。n3的时候一共只有6个排列手算都能列出来但一旦n到了8、9排列总数会膨胀到40320和362880这时候就必须靠程序系统地生成而“系统”这两个字天然就是递归的强项。顺带说一句n被限制在9以内是有道理的。n9时全排列总数是9! 362880个每个排列包含9个数字光输出就是300多万字符已经不算少了。n10的话排列数直接到3628800除非题目有特殊要求否则一般的OJ时间限制会很紧张。所以看到n9这个范围基本可以断定出题人就是想让选手用递归回溯法来解而不是搞什么高端优化。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[n1]数组标记每个数字是否被使用再用一个int path[n]数组按顺序存放已经选好的数字。这是最经典、也最容易讲清楚的写法。方案二直接在待选列表中用交换法操作序列本身不额外开used数组。这种写法代码更短但理解门槛稍高而且字典序处理不如方案一直观新手不建议从这种写法入手。我强烈建议初学者先吃透方案一。used数组是“状态”path数组是“结果路径”两者职责清晰调试的时候打印出来也容易定位问题。等你对回溯已经形成肌肉记忆再去尝试方案二也不迟。2.2 路径记录与递归终止条件的配合路径记录有一个很容易被忽视的点path数组下标和depth参数必须严格对齐。depth0表示一个数字还没选path[0]是待填的第一个位置depthn表示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开头的所有排列……由于每一层的选择都是升序的最终生成的排列序列自然满足字典序。以n3为例第一层尝试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; vectorint path; vectorbool 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的习惯性动作。全排列在n9时输出量超过三百万字符如果不去掉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)。n9时大约是362880 × 9 ≈ 326万次基本操作再算上输出字符的量级现代OJ在一秒内跑完毫无压力。但如果你试图用全排列去处理n12甚至更大指数级爆发会让你瞬间明白为什么需要更高级的搜索剪枝算法。这也是为什么很多题目把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) { vectorint 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结果n3时只输出了“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而不是\nendl除了换行还会强制刷新输出缓冲区在输出几十万行的情况下会造成巨大的性能浪费二是没有关闭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 ErrorPresentation ErrorPE是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 错题本速查表错误类型典型原因排查方向解决方案输出全是同一个排列递归返回后未恢复used状态在dfs边界和返回处打印中间状态补齐used[i]false和path.pop_back()排列数量不足终止条件或路径数组长度管理有误检查depth与path下标是否一致统一用depth作为进度游标重复排列used判断失效或path污染检查used标记与撤销是否成对出现严格按“标记-递归-撤销”顺序写运行超时n9IO同步未关闭或使用了endl检查输入输出代码加ios::sync_with_stdio(false)改用\nPresentation Error行尾多了空格复制输出到文本编辑器对比按下标控制空格输出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 递归深度与栈空间的现实问题全排列这一题的递归深度等于nn最多是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状态通过观察输出变化来理解递归的进入和退出顺序。这个方法帮我省下了大量对着代码干瞪眼的时间。等你真正理解了递归的过程调试打印自然就不需要了因为你的心里已经能跑完整个决策树了。

递归算法错题本：手写全排列吃透回溯与字典序

相关推荐

克莱姆法则到底能干嘛？一文读懂它的原理、用法与适用边界

Unity实时画面风格化实战：后处理原理、选型与性能优化

ArcGIS插件RAR包从安装到排错：识别形态、部署与打包全流程

更多资讯

数据结构——顺序表细致讲解

小白程序员必看：字节新岗位AI Agent开发火爆，如何精准入行？

AI中控与直播伴侣的联动配置和排查思路

用AI搭建一人调研团队：主编+三个AI工种+两本手册的实操框架

低代码平台岗位管理实战：用户角色权限体系的设计与落地

五大湖生态-经济耦合建模：Python实现水位、污染与渔业协同仿真

今日更新

Susi AI API实战指南：susi_alexa_skill如何用Node.js调用chat.json获取智能回答

换新电脑了？KeyStats 恢复码数据找回完全指南，端到端加密统计一键重建

重建二叉树：由前序与中序遍历序列还原二叉树的原理与 Java 实现（YCBlogs 剑指 Offer 精讲）

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？