全排列这道题不少刷题的人都见过它编号46在很多刷题平台里都排在比较靠前的位置。题目描述只有一句话给一个不含重复数字的数组比如 [1,2,3]返回它所有可能的排列。看起来简单但真正能一次写对的人说实话不算多。我见过不少人在白板上卡这道题代码写出来能跑但要么结果里出现重复要么输出的排列缺了几个更常见的是完全不知道某一步为什么要那么写一旦面试官追问就露馅。这道题之所以经典是因为它是理解“回溯算法”这把进阶钥匙最合适的锁孔。回溯的思想贯穿一大票高频题子集、组合、分割回文串、N皇后、数独求解全都能用同一套模板套进去。把这道题彻底吃透后面再遇到回溯类的题目思路会顺很多。这篇博文就是从这道题出发把回溯算法从原理到代码从坑点到扩展完整地聊一遍。适合刚接触回溯、准备面试或者刷过这道题但复盘过的人拿出来对一遍。1. 项目概述全排列到底在考什么1.1 题目需求拆解题目本身非常干净输入一个不含重复数字的数组输出它的全排列。举个例子输入[1,2,3]输出应该是[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]输出的顺序没有强制要求只要是这 6 个排列就行。一个 n 长度的数组全排列总数是 n!n 的阶乘所以输入长度为 3 时有 6 个结果长度为 4 时就是 24 个长度到 8 就已经有 40320 个了。这个数学背景非常关键它直接决定了这类题目的复杂度天花板哪怕什么都不干光是遍历一遍所有结果就已经是 O(n!)所以你别指望写一个多项式时间复杂度的解法那是不可能的。题目的约束是“不含重复数字”这个条件很善良。如果允许重复数字像[1,1,2]你还得处理去重问题那就是另一道经典题了后面第 5 节细聊。第一版代码只需要关心怎么把所有不同的排列不重不漏地生成出来。1.2 这道题真正考察的三层能力很多人觉得这道题是考“会不会递归”但我认为它实际考察的是三层递进的能力。第一层递归的直觉。你得能意识到排列可以拆解成“先固定第一个位置再排剩下的元素”这样一个子问题。固定第一个位置有 n 种选择每种选择下剩下的 n-1 个元素又是一个更小的全排列问题。这就是递归的天然结构。第二层状态的管理能力。写递归代码时最怕什么状态爆炸。你选择了一个数字放进排列里等递归返回之后这个数字必须“还回去”不然下一个分支就会带着上一步的残留状态继续跑结果全乱。这种“用完要还原”的意识就是回溯的核心素养。很多第一次写这道题的人要么忘记还原导致输出一堆重复结果要么永远卡死在一条分支里出不来。第三层复杂度洞察。你得知道全排列问题的时间复杂度是 O(n!)并且能算清楚。这考察的不是背答案而是你对递归调用树的分析能力。面试官非常喜欢在写完代码之后追问一句“这个代码的时间复杂度是多少”如果你支支吾吾印象分会大打折扣。搞清楚这三点你就明白为什么这道题被当成回溯的入门题了它代码量不大但把回溯需要的所有核心意识都浓缩在里面。2. 回溯算法的核心思路为什么全排列天生适合回溯2.1 把全排列看成一颗决策树要理解回溯最好的类比是你在一个岔路口不断做选择的迷宫。每一步都面临一个路口选哪条路都会通向一个新的路口只有走到终点才能记一条完整路径。全排列也是一样的从左往右填充结果数组的每一位每一位的选择范围是所有“还没用过”的数字。举个具体例子输入[1,2,3]第一位你可以选 1、2、3。假设你选了 1那第二位只能在 {2, 3} 里选如果第二位选了 2第三位就只能选 3。这个过程可以画成一颗树根节点是“空排列”每往下一层就多选一个数字树的叶子节点就是最终的一个完整排列。所有叶子加起来正好是 n! 个。这颗决策树就是回溯算法运行的轨迹图。回溯说到底就是“深度优先遍历”这棵树从根节点出发选择一条路走到黑走到叶子就记录结果然后掉头返回上一个路口换另一条路继续走直到把所有路口都走完。这里有个新手容易混淆的点全排列里的回溯“回”的不是上一个数字而是上一个“选择状态”。你以为自己在回去其实你是在撤销刚才的选择让这个数字重新变成“可选”状态供另一个分支使用。2.2 回溯的两个关键动作选择与撤销任何回溯算法都可以抽象成三个部分路径、可选列表、终止条件。在全排列里路径就是你已经放好的数字序列可选列表是“还没放进来的数字”终止条件是路径长度等于原数组长度。对应到代码上就是两大动作。选择动作从可选列表里挑一个数字加入路径然后递归进入下一层。进入下一层时这个数字必须从可选列表里移除否则下一层还会重复选它导致同一个排列里出现两个相同数字。撤销动作递归返回后把刚才加入路径的数字从路径尾部弹出去同时把它恢复到可选列表里。这一步不执行你的程序要么死循环在一条分支里要么最终结果大量重复、缺漏。很多人写回溯最别扭的地方就是这两个动作必须成对出现你选择了什么递归之后就必须撤销什么。我常用一句话提醒自己“递归前做的每一件事递归后都要反着做一遍。”这个对称性是整个回溯算法正确性的基石。2.3 一个通用的回溯模板回溯写得多了你就会发现大家写来写去几乎都是同一个骨架。我也总结了自己的模板见下def backtrack(路径, 可选列表): if 满足终止条件: 结果.append(路径[:]) return for 选择 in 可选列表: 做选择 # 路径.append(选择); 从可选列表中移除 backtrack(路径, 可选列表) 撤销选择 # 路径.pop(); 恢复到可选列表这个模板几乎能覆盖绝大多数回溯题。全排列里“可选列表”的表示方式有两种常见实现一种是用一个布尔数组used标记哪些索引已经被使用了另一种是直接在原数组上做元素交换用start指针区分“已经排好的部分”和“待排列的部分”。后者写出来更精简但理解门槛略高一点。下一节我把两种都展开讲清楚。3. 代码实现与关键细节3.1 最经典的写法used 标记数组版先写一个最通用、最容易理解的版本用的就是布尔标记数组。这也是我在面试中最推荐写的版本因为逻辑最直白面试官问起来也容易解释。def permute(nums): res [] path [] used [False] * len(nums) def backtrack(): # 终止条件路径长度等于数组长度说明所有位置都填满了 if len(path) len(nums): res.append(path[:]) # 注意这里用切片复制后面细说 return for i in range(len(nums)): if used[i]: continue # 做选择 used[i] True path.append(nums[i]) backtrack() # 撤销选择 used[i] False path.pop() backtrack() return res这个代码的执行过程建议你拿[1,2,3]手动跑一遍。我简单描述一下前几步外层for i in range(3)第一轮i0选择 1path[1]used[True, False, False]进入递归第二轮i0被跳过i1选择 2path[1,2]再进递归i2选择 3path[1,2,3]此时长度等于 3记录结果并返回。返回后path.pop()变成[1,2]used[2]恢复为 False然后回到上层的for循环继续i2选 3以此类推。我在给 A 同学讲解这段代码时会专门强调两个点一是used和path必须同时变更二是它们也必须同时恢复。有一个常见的错误是只回退了path忘记把used复原结果后面的循环老是跳过一些数字导致输出的排列数量不够。另一个常见错误是res.append(path)忘了切片结果res里存的其实是同一个列表对象的不同引用等回溯结束path被清空后res里所有元素都变成空列表。这就是很多人代码跑完发现输出是一堆[[], [], []]的根本原因。3.2 复杂度到底是多少面试官对这题最常见的追问就是复杂度这块得分两部分看。时间方面最直观的理解方式是“结果数乘以每个结果的复制成本”。结果数是 n!每个结果是一个长度为 n 的列表把它复制并加入res需要 O(n) 时间。因此仅收集结果这一步就是 O(n × n!)。递归过程中还有大量的节点访问和判断整体复杂度可以用 O(n × n!) 来概括。简化一点也有人直接写 O(n!)因为n相对n!来说在渐近意义上增长慢得多但从严谨角度我推荐你回答 O(n × n!)并把推导过程讲出来这比背答案更能拿到分。空间方面如果不算存储结果的空间递归深度最多到 n每层递归维护的局部变量是常数级的所以调用栈空间是 O(n)。path和used也都是 O(n)。如果把结果也算进去那当然是 O(n × n!)因为要存这么多排列。一般这题的空间复杂度回答 O(n)不计结果集就够用了。额外提醒一句n12时 n! 已经接近 4.8 亿任何语言都不可能跑完所有排列。所以刷题平台上这题给的n通常都很小算法真正有意思的地方在于写对逻辑而不是硬扛大数据量。3.3 交换法的另一种思路第二种常见实现是交换法不用额外的used数组。核心思想是把数组看成两部分前半部分是“已经排好的位置”后半部分是“待排列的元素”。每次递归都从start位置开始把start与后面某个位置的元素交换然后递归处理start1递归返回后再交换回来。def permute(nums): res [] def backtrack(start): if start len(nums): res.append(nums[:]) return for i in range(start, len(nums)): nums[start], nums[i] nums[i], nums[start] backtrack(start 1) nums[start], nums[i] nums[i], nums[start] # 交换回来 backtrack(0) return res这个版本写起来非常短而且省掉了额外的used数组。理解它的关键点是nums[:start]始终是一个正在形成的排列前缀nums[start:]是还没用过的元素。循环里把start与后面的每一个位置交换就等于尝试把每个还没用过的元素放到当前位置。交换法有个隐藏的小问题因为它是直接修改原数组并且结果存的是nums[:]的复制所以递归里的“撤销”必须把交换换回来否则下一轮循环里数组顺序会乱掉。此外这个写法在去重处理上会稍微麻烦一点需要额外考虑跳过相同数字的场景。所以我的建议是如果是新手先吃透used数组版如果代码熟练度上来了交换法可以作为备选写的快也可以但要在心里清楚它背后在干什么。4. 常见问题与排查技巧实录4.1 结果列表全是空列表或者全是同一个排列这个坑我几乎每次讲回溯都会重点说res.append(path)和res.append(path[:])的区别。path是一个列表对象res.append(path)往结果里塞的是这个对象的引用。回溯结束前path经过多次 pop最终回到空列表状态而res里所有引用都指向这个空列表所以最终打印出来是一堆空列表。如果你看到输出全是[[], [], []]基本就是这个原因。解决方法是复制一个新对象最方便的就是切片path[:]或者用list(path)。这个问题也提醒我们另一个习惯在递归里传列表时要时刻提醒自己“我是传引用还是传值”Python 里列表默认传引用真想让某个状态独立必须显式复制。这也是很多从 C 转过来的人容易踩的坑。4.2 排列数量不对或者结果有重复如果你输出的结果数量不等于 n!或者出现了重复排列那大概率是两个原因要么是used数组没有正确维护要么是撤销动作不完整。我见过一个经典的错法是在循环里这么写for i in range(len(nums)): if not used[i]: used[i] True path.append(nums[i]) backtrack() path.pop() # 忘记 used[i] False漏掉used[i] False会导致某些数字再也不会被选第二次结果自然缺一堆排列。反过来如果撤销时把不该恢复的状态也恢复了又会出现重复选择。排查这类问题最有效的办法就是拿一个小数组[1,2,3]在递归入口加一行print(path, used)顺着输出看每一步的状态变化是否符合预期。很多次我帮人排查都是五分钟内用这种打印法定位到问题。这比盯着代码干想快得多。4.3 递归写对了但还是超时怎么办全排列本身不可能低于 O(n!)如果平台给的数据量偏大导致超时先检查是不是输出本身数量巨大这是数学上绕不过去的。如果确认数据量不大却还是慢可以检查自己的代码里有没有一些无意中的高开销操作。常见的隐形开销有几个一是结果的复制不够高效比如用深拷贝copy.deepcopy(path)代替切片这在大结果集下会非常慢二是频繁的列表插入删除操作比如用path.insert(0, x)代替path.append(x)头插法是 O(n) 的而尾部追加是 O(1)三是不必要的额外判断比如把used数组换成每次遍历都重新算“剩余元素列表”这会让复杂度额外乘一个 n。我见过有人每次递归都重新构造一个available列表那性能基本就在这种地方耗完了。另外如果是交换法尽量在原数组上直接交换不要再额外复制一份数组传入递归。复制数组本身是 O(n)每层递归都复制整体开销就上去了。4.4 一道题两个版本面试时优先写哪种这个私下里也经常有人问我。如果面试目标是快速写对且让面试官容易理解我强烈建议写used数组版因为它和回溯模板的对应关系最直观“选择一条路、撤销选择”这两个动作一目了然。交换法虽然短但如果面试官不熟悉这个技巧你得额外花时间解释为什么交换之后要再交换回来容易把思路绕偏。当然如果这道题你已经非常熟练写交换法也没问题它胜在省空间、代码短。但从我长期面试别人的经验看大多数面试官更关注你能不能把回溯过程解释清楚而不是代码是不是最短。面试时把自己放在“让对方听懂”的位置通常比展示花哨技巧更稳。5. 扩展有重复元素与更广的应用5.1 有重复元素该怎么处理如果原题把“不含重复数字”改成“可能包含重复数字”刷题平台上有这道题的进阶版编号是 47那么简单的used数组就不够了因为两个相同数字会被当成两个不同的选择产生重复排列。去重思路也不复杂核心一句话在“同一层递归的同一轮 for 循环里”如果遇到同样的数字只处理第一次后面直接跳过。但是要注意“同一层”这个限定之前有人误把所有相同的都跳过结果把正确排列也跳掉了因为不同层之间同一个数字是可以再次使用的比如数组中本来就有两个 1。实现时先把数组排序然后在循环里加一个剪枝判断if used[i]: continue if i 0 and nums[i] nums[i-1] and not used[i-1]: continue这个not used[i-1]很关键它表示“前面那个相同的数字在当前递归分支中还没被使用”。如果它在分支里已经被用过了说明当前这个相同数字可能是不同层级的复用可以继续如果它没被用过说明你在同一层正准备再次选择相同数字这就是重复直接跳过。这个写法我推荐死记下来因为它是面试中出现频率极高的一个小细节。5.2 全排列的兄弟题型子集、组合、分割、棋盘吃透全排列之后回溯类的其他题目都会变得顺手。子集问题就是把“填满所有位置”换成“收集所有中间状态”组合问题是在循环里加一个start参数避免回头选择已经选过的数字分割回文串问题是把“选择数字”抽象成“选择一个子串”N 皇后问题则把“选择一个数字”换成“在一行中选择一个安全的列位置”。你会发现这些题的内核都是同一个模板终止条件、路径、可选列表、做选择、递归、撤销选择。区别只在于“可选列表”的定义和“终止条件”的设定方式。所以与其一道一道死记不如把全排列这一道彻底弄明白后面是举一反三的过程。5.3 全排列的算法在现实里长什么样有人会问全排列除了面试还有什么用真实场景里其实出镜率不低。我举几个例子密码爆破工具会枚举字符的所有排列组合旅行商问题的暴力求解版本会枚举所有城市的访问顺序然后计算总路程测试人员在写接口用例时经常需要穷举某些参数的排列顺序来覆盖所有场景甚至在你给几个人安排值班顺序、给几个任务排执行顺序时本质上都是在求全排列后按条件筛选。虽然真实工程里 n 一变大就会改用启发式算法或者剪枝但全排列这种暴力枚举的思路依然是很多算法的最后兜底方案。我个人在带新人时经常用这道题做“算法思维体检”看一个人拿到题之后会不会先想清楚状态维度、会不会主动分析复杂度、能不能解释清递归调用树的形状。这三个点都过关基本可以断定他写其他回溯题也不会太吃力。全排列的价值不在于题目本身多么复杂而在于它是打开一串算法题门的钥匙。花一个下午把这道题啃透再连着刷两三个变体题比刷十道不相关的题都管用。