全排列这道题几乎是每个刷算法题的人都会撞上的第一道DFS。我当年第一次见到“输入[1,2,3]输出所有排列组合”的时候脑子里全是循环套循环的画面——三个数还好说五个数、八个数怎么办循环层数根本没法写死。直到理解了DFS的递归结构才发现这类“穷举所有可能”的问题本质上都长着同一张脸。这篇文章不打算只贴一份代码而是把全排列当成一个解剖样本把DFS模板拆开揉碎为什么递归能代替多层循环path、used、回溯这三个角色分别在干什么以及怎么从这个模板长出组合、子集、排列去重等其他变体。无论你是刚学递归的新手还是准备面试想快速捡起回溯模板的熟手这篇文章都值得看完——尤其是后半部分的坑和优化全是真实做题时踩出来的经验。1. 全排列问题在考什么穷举背后的决策树模型先明确问题本身。给定一组不含重复数字的数组比如[1,2,3]要求返回所有可能的排列1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1一共6种正好是3!。对于长度为n的数组全排列数量是n!这意味着穷举本身就无法避免指数级的枚举规模。所以这道题考察的不是“怎么才能少算”而是“怎么用清晰可扩展的结构把每种可能都完整地枚举出来”。1.1 为什么多层循环写不出来很多人第一反应是几个数就写几层循环。三个数就三层for循环四层就四层。这个思路能跑通[1,2,3]但对[1,2,3,4,5,6]就彻底崩了——循环嵌套的层数必须等于数组长度而数组长度在写代码的时候根本不知道。就算用python的itertools.permutations那也只是别人封装好的结果遇到面试官追问“底层怎么实现的”照样答不上来。核心矛盾是循环的层数是静态的、写死的而全排列的规模是动态的、随输入变化的。需要一个结构让“层数”自己跟着问题规模走——这就是递归的价值每一层递归处理一个位置递归深度天然等于排列长度。递归把“层数不确定”的问题转换成了“递归深度由参数控制”的问题。1.2 把排列过程画成一棵决策树想象你在玩一个填空游戏有n个空位从候选数字里一个一个挑数字填进去。每填一个位置就面临一次选择剩下的数字里选哪个选了A就不能再选A然后进入下一个空位继续选。这个决策过程展开之后是一棵树根节点一个空排列。第一层从所有数字里选一个产生n个分支。第二层每个分支下从剩余数字里再选一个产生n*(n-1)个分支。直到第n层所有位置填满产生n!个叶子节点。DFS遍历这棵树的方式是“一条路走到黑”——从根出发沿着某个分支一路填到底得到一个完整排列然后回退一步换另一个选择再走到底。这种“往前走、走到头、退回来、换条路再走”的过程就是DFS对决策树的遍历方式。理解了这个模型再看代码模板每一行都有明确对应物。2. 最经典的DFS模板逐行拆解以C为例直接看最通用的一份模板代码语言用的是C。你用Java、Python、JavaScript结构也一模一样只是语法层面的差别。class Solution { private: vectorvectorint result; // 收集所有合法排列 vectorint path; // 当前正在构造的排列 vectorbool used; // 标记某个数字是否已被使用 void dfs(vectorint nums) { if (path.size() nums.size()) { result.push_back(path); // 填满了记录答案 return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; // 已经用过的数字跳过 used[i] true; path.push_back(nums[i]); // 做选择 dfs(nums); // 进入下一层决策 path.pop_back(); // 撤销选择 used[i] false; // 恢复状态 } } public: vectorvectorint permute(vectorint nums) { result.clear(); path.clear(); used.assign(nums.size(), false); dfs(nums); return result; } };这段代码只有二十来行但它几乎涵盖了DFS回溯的全部核心要素。我逐行说清楚每个角色存在的理由。2.1 path记录当前路径代表决策树中“当前走到哪个节点”path是一个动态数组里面存的是当前正在构造的排列的前缀。path.size()等于已填数字的个数也等于递归深度。当path.size() nums.size()时说明所有位置都填满了当前的path就是一个完整排列直接拷贝进result。这里有个细节为什么是result.push_back(path)而不是result.push_back(nums)之类的因为path正是我们一路做选择累积出来的结果。注意push_back会拷贝一份path的副本这很重要。如果存的是引用或指针后面path.pop_back()会把已经记录好的答案破坏掉。所以拷贝是必须的不是性能浪费而是数据安全。2.2 used数组记录“哪些数已经用掉”对应决策树的剪枝used是一个布尔数组used[i] true表示nums[i]已经出现在当前path中不能再选。它的作用是防止同一个数字在同一排列里被重复使用。为什么需要这个数组因为全排列的约束是“每个位置选一个数且每个数只能选一次”。没有used的话第一层选了1第二层还能继续选1那最后会生成[1,1,1]这种不合法的排列而且递归永远不会停止。used数组本质上是决策树上的剪枝条件——遍历时跳过已经走过的分支。有的同学会疑惑那能不能不建数组直接在path里查“某个数在不在”可以但那是O(n)的线性查找每次递归都要扫一遍path。用数组标记是O(1)的查询而且代码意图更清晰。n很小的时候无所谓n大了或者递归层数深了效率差距就很明显。2.3 递归调用与回溯DFS的核心动词“前进”和“后退”递归调用的位置在for循环内部。dfs(nums)这一行表示“当前这层已经确定了第path.size()个位置的数字继续去填下一个位置”。这是DFS的“前进”。但真正精妙的是递归调用之后的这段代码path.pop_back(); used[i] false;这两行叫“回溯”或者“撤销选择”。它们的作用是当递归返回时把刚才做的选择全部还原让path和used回到进入递归之前的状态然后才能尝试循环里的下一个候选数字。如果没有回溯会出现什么情况第一轮循环选了1递归把所有以1开头的排列都枚举完了回到根节点时如果不把1拿掉path里一直是[1,...]而且used[0]一直是true导致第二个分支以2开头根本没法开始。所以回溯不是可选步骤而是让循环能继续枚举下一个分支的前提条件。这就像你在迷宫里走完一条路退回到岔路口时必须收回你迈出的那只脚才能迈上另一条路。2.4 递归结束条件什么时候算“找到了一个答案”结束条件是path.size() nums.size()也就是所有位置都填满了。这里注意判断时刻的选取是在“进入下一层之前”判断还是在“进入下一层之后”判断这份模板选择的是进入递归后先判断是否填满填满就记录并返回。这样叶子节点也会执行一次函数调用多消耗一点栈空间但逻辑统一、简洁。另一种写法是在调用之前先判断“下一层会不会满”满的话直接记录再返回能省掉一层无效调用。两种写法都能过我推荐模板这种因为判断条件集中在一处出错概率低。2.5 为什么这份模板能被称为“模版”把这段代码的骨架抽象出来去掉具体业务逻辑你会看到这样一个结构递归函数() { if (满足结束条件) { 记录答案; return; } for (所有候选选择) { 剪枝掉不合法的选择; 做选择; 递归进入下一层; 撤销选择; } }这个四步结构——剪枝、选择、递归、回溯——可以套到大量的“枚举所有解”类问题上。组合、子集、N皇后、数独、括号生成、电话号码字母组合……本质上都是这个骨架换了一层皮。这就是为什么面试和竞赛里管它叫“DFS模板”你不需要每次重新设计递归结构只需要改动结束条件、候选集合、剪枝规则这三处就能解决一大类题目。3. 从模板到变体组合、子集、去重排列都能长出来模板背下来只算入门真正会用是另一回事。我认为全排列模板的核心价值在于它是理解其他回溯问题的一把钥匙。下面讲三种最常见的变体你会发现它们和全排列的差异只是“改三处”而已。3.1 组合问题把全排列的“顺序敏感”改成“顺序无关”组合问题长这样从[1,2,3,4]里选2个数有多少种组合结果是[1,2]、[1,3]、[1,4]、[2,3]、[2,4]、[3,4]共6种。注意[1,2]和[2,1]在组合里算同一种。所以组合问题要避免“1选了2之后2又回头选1”这种反向选择。实现方法是在递归函数里加一个参数start表示下一层只能从nums[start]开始选void dfs(vectorint nums, int start, int k) { if (path.size() k) { result.push_back(path); return; } for (int i start; i nums.size(); i) { path.push_back(nums[i]); dfs(nums, i 1, k); path.pop_back(); } }仔细对比这里没了used数组加了start索引。为什么因为组合只关心选了哪些数不关心顺序所以用“下标递增”天然保证不会回头选之前的元素。而且组合中每个元素最多出现一次靠i1控制了递归层级的起始位置就不需要额外标记是否使用过。这个变体很好地说明了模板的每个组件都是按需取用的。used和start都是控制“选择空间”的手段根据题目约束选用其一或两者并用。3.2 含重复数字的排列去重剪枝的进阶用法原始全排列假设数组无重复元素比如[1,2,3]。如果输入变成[1,1,2]直接套模板会出问题两个1互相交换得到的排列是重复的比如[1a,1b,2]和[1b,1a,2]在数值上完全一样但代码会当作两个答案输出。解决思路是先排序再在循环里跳过“重复且前一个相同元素没被使用”的分支。代码如下void dfs(vectorint nums) { if (path.size() nums.size()) { result.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; if (i 0 nums[i] nums[i-1] !used[i-1]) continue; used[i] true; path.push_back(nums[i]); dfs(nums); path.pop_back(); used[i] false; } }关键的剪枝条件是nums[i] nums[i-1] !used[i-1]。这行的含义是当前数字和前一个数字值相同并且前一个数字在当前路径中还没被使用那么跳过当前数字。怎么理解这个条件排序之后相同的数字聚在一起。它们在决策树中是一组“等价分支”。为了只走第一个分支规定“同一个数值的分支只有第一个被优先使用”。如果前一个相同数字还没用过说明当前处于同一层级的后续分支和之前已经走过的分支是重复的直接剪掉如果前一个已经用过了说明是在更深的层级允许继续使用。这个剪枝手法在很多去重类问题里都会碰到理解了“!used[i-1]配合排序实现同层剪枝”这一条其他变体都能举一反三。3.3 子集问题把“填满”改成“随时可以记录”子集问题是给定[1,2,3]输出所有子集包括空集。和全排列的差异在于全排列要求path.size()等于数组长度才算答案而子集问题中任何长度的path都是一个合法子集。所以模板变化极小——把记录答案的时机提前到递归开头而不是等到叶子void dfs(vectorint nums, int start) { result.push_back(path); // 每个节点都是答案 for (int i start; i nums.size(); i) { path.push_back(nums[i]); dfs(nums, i 1); path.pop_back(); } }这里甚至没有显式的结束条件因为循环遍历完后函数就自然返回了。子集问题展示了一个很重要的思路转变结束条件不是“必须填满”而是“当前状态本身就是答案”。做题时多想一步“什么样的状态是一个合法解”比死记结束条件管用得多。4. 实测中常踩的五个坑以及一个值得掌握的swap优化代码能跑通是一回事跑得对、跑得快、面试时能讲清楚是另一回事。下面这些坑我自己刷题和帮别人review代码时都撞见过列出来帮你省些弯路。4.1 坑一记录答案时忘记拷贝result.push_back(path)如果写成result.push_back(path)没问题这是值拷贝。但如果图省事存了path的引用或者指针比如把result定义成vectorvectorint*那么后续path.pop_back()会改变所有已存答案的内容最终结果全是空数组或同一个数组。这个坑的根本原因是回溯过程中path是一个不断变化的状态而合法答案要求的是“某一时刻的状态快照”。快照必须独立于状态存在不能共用一个可变对象。理解这个本质后任何语言都不会踩这个坑——Python里如果用result.append(path[:])而不是result.append(path)同样是拷贝问题。4.2 坑二状态未在递归返回后复原used[i] true之后调用了dfs返回后忘记把used[i]复位或者只复位置了used却忘了path.pop_back()。这样下一轮循环会使用残留状态导致枚举结果奇奇怪怪甚至死循环。一个有效的自查方法是保证“做选择”和“撤销选择”的代码在递归调用前后严格对称。used[i] true对应used[i] falsepath.push_back对应path.pop_back。凡是破坏了对称性的代码百分之百有逻辑错误。我写回溯代码时习惯把“做选择”和“撤销选择”两行紧挨着写中间只夹着一行递归调用这样视觉上就能看出对称性。4.3 坑三递归结束条件写在错误的地方有的同学会把结束条件放在for循环之前提前判断导致path为空时直接进入循环、非空时又跳过循环逻辑混乱。正确的判断位置只有两处递归函数开头先判后选或者for循环底部先选后判。选一即可但不要混用。我建议统一放在递归函数开头理由在刚才已经说过判断集中、代码结构统一。尤其是子集、组合这种“中间状态也是答案”的问题放在开头天然贴合。4.4 坑四把used数组和start参数混用错位组合问题用了start全排列用了used两者各自的语义不同。但也有的问题同时需要两者比如组合总和II数字有重复且不能重复使用同一个位置。这时候最容易犯错的是用了start控制起始位置却忘了used去处理同值剪枝或者有used却不传start导致重复组合。做题时先问自己两个约束一是“元素能不能重复使用”二是“顺序算不算不同结果”。前者决定需不需要start/used后者决定问题是排列还是组合。这两个问题想清楚了模板怎么调整就清楚了。4.5 优化用交换(swap)代替path和used标准模板用path加used已经足够应付绝大多数场景。但如果你追求更短的代码和更少的空间可以改用交换法实现全排列。思路很巧妙完全不再维护path和used而是直接在原数组上通过交换数字来构造排列。每次递归处理位置idx时把nums[idx]和nums[i]交换使得nums[0...idx]这一段是已经确定的排列前缀void dfs(vectorint nums, int idx) { if (idx nums.size()) { result.push_back(nums); return; } for (int i idx; i nums.size(); i) { swap(nums[idx], nums[i]); dfs(nums, idx 1); swap(nums[idx], nums[i]); } }这个写法的优点是省掉了used数组和path数组空间占用更小代码更紧凑。缺点是修改了原数组而且对“元素重复”的去重需要额外处理先排序再在循环里判断nums[i]是否在[idx, i)区间内出现过。面试时用它讲“排列的生成过程”会更直观但日常练习建议先从pathused学起理解透了再优化。4.6 关于递归深度的实际限制全排列的时间复杂度是O(n!)也就是递归树节点数。空间复杂度是递归栈深度O(n)加上path和used的O(n)。对C来说递归深度达到几千层就可能爆栈但全排列n一大比如n12以上n!早就大得没法在限定时间内跑完了。所以实际竞赛和面试场景中n基本不会超过8到10。这个约束条件意味着不用担心递归栈溢出更值得担心的是剪枝不够导致枚举分支过多。我在LeetCode上实测过n8的[1,2,3,4,5,6,7,8]全排列有40320个结果模板代码用时在毫秒级n10就来到3628800个结果已经接近一秒的边缘。所以如果遇到n10以上的全排列大概率不是让你直接枚举而是配合约束条件做剪枝或者题目本身考察的是别的算法。5. 模板的边界感什么时候该用DFS什么时候该掉头最后想聊一点使用场景的问题。模板是工具不是万能钥匙。面试或者做题时遇到“枚举所有可能性”的问题先花十秒钟判断它的规模和解空间性质。如果解空间是排列组合级别的而且要求输出所有具体方案DFS回溯几乎是唯一的选择。最典型的就是全排列、组合、子集、分割回文串、N皇后、岛屿类问题。它们共同的特点是解由多个决策步骤组成每步有若干选项选项间有约束最终答案数量有限但可能很多。但如果问题只要求“知道有多少种方案”不要求“列出方案”优先考虑DP或者数学公式。比如“n个数的全排列有多少种”答案是n!不需要DFS。这是很多新手容易犯的错——为一个只需要答案数量的问题写了一大段回溯代码其实完全没必要。另外有一种情况要特别警惕解空间虽然是“所有可能的排列”但存在“最优解”这一说法。这时候DFS的职责是配合剪枝、分支限界找到最优解而不是把所有方案都枚举完。最典型的就是旅行商问题TSP、八皇后、数独求解——DFS在这些问题里要搭配“当前状态已经不可能优于已知最优解”的判断提前终止分支。我在实际刷题中的体会是把全排列这道题当成DFS模板的“锚点”是最划算的学习路径。先用它把“选择、递归、回溯、结果记录”这四个动作练成肌肉记忆然后遇到任何回溯类题目先问自己“这和全排列的模板差在哪三行代码”而不是从零设计递归。这个思维习惯帮我节省了大量思考时间也让面试写代码时手稳得多。到这里全排列模板的核心内容已经讲完了。记住那个四步骨架剪枝过滤非法选择做选择推进状态递归深入下一层回溯还原现场。它写起来简单但背后是整个搜索算法思想的浓缩——理解了它你会发现所谓套路其实是把“穷举所有可能”这件事组织得清晰、有边界、可控制。如果这篇文章能帮你迈过递归这道坎那分享的目的就达到了。