LeetCode 47 这题我每次带人刷回溯专题都会把它放在一个很特殊的位置全排列 I 的进阶版也是“去重剪枝”的入门必修课。如果说 46 题教会你回溯的基本框架那 47 题就是逼着你想清楚一件事——数组里明明有重复数字为什么最终的排列结果里不能有重复排列。很多人解法能跑通但一旦被问到“为什么去重条件要写 !used[i-1] 而不是 used[i-1]”就直接卡壳。这篇文章就把它彻底讲透从题面、原理、代码到排查一条龙聊完。适合刚刷完 46 题、准备系统过一遍回溯专题的人也适合面试前想快速复习排列类去重模板的人。1. 先看懂这题重复元素带来的去重难题1.1 题面到底说了什么和 46 题差在哪先看题目本身。给定一个可包含重复数字的序列 nums按任意顺序返回所有不重复的全排列。示例很典型nums [1,1,2]输出是 [[1,1,2],[1,2,1],[2,1,1]]一共 3 个。注意[1,1,2] 这个结果里出现了两个 1这是允许的——题目说的是“不重复的全排列”指的是排列结果之间不能重复而不是排列内部不能有重复数字。这个理解一旦错了后面代码思路全歪。和 46 题全排列 I 相比唯一的区别就是数组里多了重复元素。46 题的 nums 是互不相同的直接用最基础的回溯模板就能过。但 47 题的输入里可能有重复如果你原封不动套 46 题的模板跑出来的结果会有一堆重复排列。很多人第一次提交就是因为没做任何去重处理直接在一堆重复答案里怀疑人生。举个例子nums [1,1,2] 不剪枝的话排列会输出 6 个其中 [1,1,2] 和 [1,2,1] 都会出现两次因为两个相同数字 1 在不同的位置被选中了最终生成了相同的序列。这就是 47 题的核心难点去重。1.2 为什么去重会成为“核心难点”从回溯的角度看46 题的主框架非常清晰维护一个 path 和一个 used 数组每次从没用过的数字里挑一个加入 path递归下一层回溯时恢复现场。这个框架本身不复杂复杂的是“怎么判断这次选择是不是重复的”。重复的本质是什么两个数值相同的数字在同一个递归层级的 for 循环里如果它们都作为“第一个元素”被选中那它们往下展开的搜索树是完全一样的。比如 [1,1,2]在第一层选第一个 1 和选第二个 1生成的排列序列一模一样。所以在同一层里相同的值只能被选一次。这个直觉很多人都能有但落到代码上怎么优雅地实现就有讲究了。目前主流的去重路线也就两种第一种是排序 used 数组剪枝这也是我觉得面试中最值得掌握的写法第二种是每层递归用哈希集合去重不用排序也能做。还有一种是交换法 每层哈希集合属于第三种写法代码简洁但不那么好理解。我接下来的篇幅会主要围绕第一种展开因为它最能讲清楚去重的本质。2. 去重原理排序剪枝的四种情况全拆解2.1 先建立回溯主框架不管怎么去重回溯主体是固定的。我先把 46 题的模板写出来这是理解 47 题的基础private void backtrack(int[] nums) { if (path.size() nums.length) { res.add(new ArrayList(path)); return; } for (int i 0; i nums.length; i) { if (used[i]) continue; used[i] true; path.add(nums[i]); backtrack(nums); path.removeLast(); used[i] false; } }这个框架里used[i] 表示 nums[i] 是否已经被当前路径用过。因为 46 题没有重复元素所以只要保证“同一个位置不选两次”结果自然不重复。但 47 题里有两个位置的值是一样的比如 nums[0] 1、nums[1] 1如果你不区分“值重复”和“位置重复”就会出现重复排列。2.2 排序去重条件为什么是 nums[i] nums[i-1] !used[i-1]核心剪枝就一行if (i 0 nums[i] nums[i - 1] !used[i - 1]) { continue; }这一行必须配合 Arrays.sort(nums) 使用。排序的目的是让相同的数字排在一起这样判断 nums[i] nums[i-1] 才有意义。如果相同数字不相邻那这个条件根本触发不了去重就失效了。要理解这行代码为什么这么写得把它拆成两部分看。前两个条件 nums[i] nums[i-1] 说明“当前元素和前一个元素值相同”这是重复的前提。真正的关键是第三个条件 !used[i-1]它表达的是“前一个相同值的元素在当前这层 for 循环中还没有被选中过”。我这么说可能有点抽象。换个说法在同一层递归里如果 nums[i-1] 和 nums[i] 值相同而且 nums[i-1] 没被用过那说明 for 循环刚从 nums[i-1] 这个分支走出来或者即将处理到它前面的分支。这时候再选 nums[i]就会产生和刚才那个分支一模一样的搜索子树。所以必须跳过。反过来如果 used[i-1] 为 true说明 nums[i-1] 是被当前路径上更早的层选中的它属于“已经用掉的数字”。这种情况下再选 nums[i] 是完全合法的因为排列内部允许相同数字出现在不同位置。我见过很多新手在这行翻车把条件误写成 used[i-1]结果答案少了一大堆。为什么你想想 [1,1,2] 这个例子排序后第一个分支选了 nums[0]1进入下一层后used[0] 是 true。在第二层 for 循环走到 i1 时nums[1] 也等于 1如果此时用 used[i-1] 作为剪枝条件就会把这个合法分支剪掉[1,1,2] 这个答案直接没了。所以记住了排列类去重剪的是“同一层 for 循环里的重复选择”必须用 !used[i-1]。2.3 set 去重方案不排序也能做的替代写法如果不排序也可以用每层递归新建一个 HashSet 来去重。核心思路是既然同一层不能选相同的值那就在这一层的 for 循环里用一个 set 记录已经选过的值一旦再次遇到就直接跳过。参考写法private void backtrack(int[] nums) { if (path.size() nums.length) { res.add(new ArrayList(path)); return; } SetInteger seen new HashSet(); for (int i 0; i nums.length; i) { if (used[i]) continue; if (!seen.add(nums[i])) continue; used[i] true; path.add(nums[i]); backtrack(nums); path.removeLast(); used[i] false; } }这里 seen 每次进入递归时都会 new 一个它只对当前这一层生效。即使 nums[0] 和 nums[1] 都是 1只要这层已经选过一次 1下次再遇到就跳过。这样做的好处是原数组顺序不会被破坏而且不用先排序。坏处是每层都额外维护一个 set空间开销略高递归深度大时栈上会同时存在多个 set。排序剪枝和 set 剪枝各有优势。我个人的建议是面试时优先写排序版本因为代码看起来更“有设计感”而且剪枝时机更直观面试官问起来你也好解释。如果你实在不喜欢排序set 版本至少有“不用排序”这个优势适合快速 AC。3. 完整实现两种主流代码与复杂度推导3.1 版本 A排序 全局 used 数组这是我认为最稳健、最好讲的版本完整 Java 代码如下class Solution { ListListInteger res new ArrayList(); LinkedListInteger path new LinkedList(); boolean[] used; public ListListInteger permuteUnique(int[] nums) { Arrays.sort(nums); used new boolean[nums.length]; backtrack(nums); return res; } private void backtrack(int[] nums) { if (path.size() nums.length) { res.add(new ArrayList(path)); return; } for (int i 0; i nums.length; i) { if (used[i]) continue; if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue; used[i] true; path.add(nums[i]); backtrack(nums); path.removeLast(); used[i] false; } } }Python 的写法基本等价class Solution: def permuteUnique(self, nums: List[int]) - List[List[int]]: nums.sort() n len(nums) res [] path [] used [False] * n def backtrack(): if len(path) n: res.append(path[:]) return for i in range(n): if used[i]: continue if i 0 and nums[i] nums[i - 1] and not used[i - 1]: continue used[i] True path.append(nums[i]) backtrack() path.pop() used[i] False backtrack() return resC 版本也不复杂只是 lambda 捕获稍加注意class Solution { public: vectorvectorint permuteUnique(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint res; vectorint path; vectorbool used(nums.size(), false); functionvoid() backtrack []() { if (path.size() nums.size()) { res.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]); backtrack(); path.pop_back(); used[i] false; } }; backtrack(); return res; } };三个版本逻辑完全一致。提交之后耗时表现都不错因为输入规模上限只有 8排序的 O(NlogN) 开销可以忽略不计。3.2 复杂度推导时间为什么是 O(N×N!)先看时空复杂度。最坏情况下输入没有重复元素47 题退化成 46 题排列数是 N!。每个叶子节点都要把 path 复制一份放进结果集复制需要 O(N) 时间。而在搜索过程中每个递归节点都要进行一次 for 循环遍历遍历长度最多是 N。所有节点的数量级其实也是 O(N!)所以总时间可以近似表述为 O(N×N!)。空间复杂度主要拆三块递归栈深度 O(N)path 和 used 数组各 O(N)结果集 res 占 O(N!×N)。如果只看算法本身不算输出额外空间就是 O(N)。如果算上存储答案的空间就是 O(N×N!)。排序版本的额外空间基本就是 O(N)set 版本则因为每层都要维护一个 set递归栈上所有 set 的总大小在最坏情况下接近 12...N O(N^2)。LeetCode 这题的 n 最大 8所以空间都是小事不用担心超限。3.3 交换法写法了解即可还有一种写法不借助 used 数组而是通过交换元素来生成排列同时用每层的 HashSet 去重。核心思路是从 start 位置开始把 nums[start] 和后面每一个元素交换然后递归处理 start1。代码如下class Solution { ListListInteger res new ArrayList(); public ListListInteger permuteUnique(int[] nums) { backtrack(nums, 0); return res; } private void backtrack(int[] nums, int start) { if (start nums.length) { ListInteger list new ArrayList(); for (int n : nums) list.add(n); res.add(list); return; } SetInteger seen new HashSet(); for (int i start; i nums.length; i) { if (!seen.add(nums[i])) continue; swap(nums, start, i); backtrack(nums, start 1); swap(nums, start, i); } } private void swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; } }这个写法能过但这道题我不推荐你主用。原因是交换会打乱数组原有顺序导致“相邻相同值”的判断不可靠必须靠 set 才能去重。而 set 又要在每个递归层新建你不能用一个全局 set否则会误伤不同分支的选择。理解交换法需要脑海里额外维护一层“数组当前状态”的模拟对新手不太友好。如果你是为了扩展视野可以读一读如果是为了面试稳定输出排序 used 版本够用了。4. 手推一遍[1,1,2] 的完整回溯树4.1 一步一步看剪枝怎么生效光看代码还是不够我建议你跟着我手动推一遍。排序后 nums [1,1,2]初始 used [false, false, false]。第一层递归path []i0nums[0]1used[0]false。i0 不满足 i0 条件不剪选择 nums[0]used[0]truepath[1]进入第二层。第二层返回后恢复 used[0]falsepath[]。i1nums[1]1used[1]false。此时 nums[1]nums[0]且 used[0]false!used[0]true条件成立跳过。i2nums[2]2和前面的 1 不相等选择 nums[2]used[2]truepath[2]进入另一个分支。所以第一层实际只有两个选择选第一个 1或者选 2。第二个 1 在第一层被剪掉了这就避免了 [1,1,2] 和 [1,1,2] 同时在结果集里出现两次。再看选择 nums[0]1 后的第二层path[1]used[true,false,false]i0used[0]true跳过。i1nums[1]1used[1]false。剪枝判断i0 成立nums[1]nums[0] 成立!used[0]!truefalse整个条件不成立所以不剪选择 nums[1]path[1,1]进入第三层。i2nums[2]2used[2]false且不等于前面的值选择 nums[2]path[1,2]进入另一个第三层分支。这里就是关键第二层的 i1 不能剪因为这是在排列内部选择第二个 1排列结果是 [1,1,2]完全合法。也正是因为这里不剪!used[i-1]这个条件才站得住脚。第三层只剩最后一个元素可放path[1,1] 时只能放 nums[2]2得到 [1,1,2]。path[1,2] 时只能放 nums[1]1得到 [1,2,1]。选择 nums[2]2 的那条第一层分支同样道理往下推会得到 [2,1,1]。最终 3 个结果刚好是答案。我把这个过程整理成一张表方便你对照剪枝点层数当前 pathfor 循环走到 i 的值剪枝判断结果动作1[]i0, 值 1i0 不剪选择进入下一层1[]i1, 值 1nums[1]nums[0] !used[0]剪掉1[]i2, 值 2不等于前一个值选择进入下一层2[1]i0, 值 1used[0]true跳过2[1]i1, 值 1used[0]true 导致条件不成立选择不剪2[1]i2, 值 2不相等选择不剪3[1,1]i2, 值 2唯一可选项选择加入结果3[1,2]i1, 值 1唯一可选项选择加入结果这张表我建议你自己也在纸上画一遍。刷回溯题最忌只看不推手动推演三四个用例后很多疑问会自然消失。4.2 边界情况与输入陷阱LeetCode 47 的 nums 长度范围是 1 到 8不需要处理空数组但代码里还是要养成“判空”的习惯万一以后题目改了或者你在公司内部平台遇到变种题呢。单元素数组的情况也要心里有数nums[1]输出 [[1]]回溯会直接进入递归终止条件不会进 for 循环。还要注意数值范围是 -10 到 10包含负数。排序后负数会排在最前面去重条件 nums[i]nums[i-1] 对负数同样生效这一点和正数没有区别。但如果你用 set 去重别把值直接当作数组下标使用这是新手常踩的坑——数组下标不能是负数而这里完全可以用 HashSet没必要用计数数组。输入里如果重复元素更多比如 [1,1,1]排序后相同元素连成一片去重逻辑会把这棵树剪得非常干净最终结果只有 [1,1,1] 一个。你可以试着手推一下加深对“同层剪枝”的理解。5. 实战排错常见报错与踩坑记录5.1 最典型的三个错误第一个错误忘记排序。去重条件写的是 nums[i] nums[i-1]如果数组没排序相同的值可能隔得很远这个判断根本不会触发。表现就是输出去重失败答案里有大量重复排列。排查方法很简单先在主函数开头加 Arrays.sort(nums)再跑测试用例。第二个错误把 !used[i-1] 写成 used[i-1]。这个错误的典型表现是输出结果少了几个合法排列。比如 [1,1,2] 会输出 [[1,2,1],[2,1,1]]少了 [1,1,2]或者更乱。原因我在前面章节已经详细拆解过了总结成一句话排列题里同一路径上使用重复元素是合法的要剪的是同一层的重复选择。第三个错误用全局 HashSet 去重。有些人看到“重复数字”第一反应是搞一个全局 set 来记录所有选过的值结果是整棵搜索树被剪得只剩一条路径。这个问题常见于从“组合总和”类题目转过来的选手因为组合题里的 set 用法和排列题完全不同。排查时可以打印一下每次进入递归时的 path看看是不是从第一层就只剩一个分支了。我整理了一张表方便大家对照错误类型典型现象问题本质解决方案忘排序输出重复排列相邻相同值判断失效主函数先排序用 used[i-1]输出缺失排列剪掉了合法分支改成 !used[i-1]全局 Set输出明显过少跨层误剪每层新建 Set或改用排序剪枝交换法忘还原排列错乱数组状态污染递归后必须 swap 回来5.2 调试技巧让回溯过程可视化刷回溯题最高效的调试方式就是打印递归树。我常用的办法是在 backtrack 函数开头加一个 depth 参数打印的时候带缩进private void backtrack(int[] nums, int depth) { StringBuilder sb new StringBuilder(); for (int j 0; j depth; j) { sb.append( ); } System.out.println(sb 进入递归 depth depth , path path); if (path.size() nums.length) { res.add(new ArrayList(path)); System.out.println(sb 加入结果: path); return; } for (int i 0; i nums.length; i) { if (used[i]) continue; if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue; used[i] true; path.add(nums[i]); backtrack(nums, depth 1); path.removeLast(); used[i] false; } }配合 [1,1,2] 跑一遍输出会非常直观你会在第一层看到 i1 那个分支被跳过然后立刻理解“同层剪枝”的真实含义。我用这个方法带过不少人基本上一到两个用例就能让思路清晰。调试时还有个技巧先跑 [1,1,2] 验证结果数量是 3再跑 [1,2,2] 验证结果数量是 3最后跑 [1,1,1] 验证结果是 1。这三个用例覆盖了所有典型场景。如果你能把这几个小用例的输出正确性验证清楚这道题基本就没问题了。6. 这套去重思路能迁移到哪些题6.1 姊妹题子集 II 与组合总和 II刷题最忌讳孤立地刷一道题。47 题的去重思想稍微调整一下就能迁移到另外两题子集 II 和组合总和 II。它们的共同点是数组里有重复元素输出不能有重复集合。以子集 II 为例排序 剪枝的核心思路完全一样只是递归方式从“每次从头开始选”变成“从 start 开始选”class Solution { ListListInteger res new ArrayList(); LinkedListInteger path new LinkedList(); public ListListInteger subsetsWithDup(int[] nums) { Arrays.sort(nums); backtrack(nums, 0); return res; } private void backtrack(int[] nums, int start) { res.add(new ArrayList(path)); for (int i start; i nums.length; i) { if (i start nums[i] nums[i - 1]) continue; path.add(nums[i]); backtrack(nums, i 1); path.removeLast(); } } }注意这里去重条件直接写成 i start nums[i] nums[i-1]不需要 used 数组。因为子集类题目是“组合式”的同一层去掉重复值即可而层内重复判断靠 start 就能实现。这和 47 题的区别刚好体现了“排列用 !used[i-1]组合用 i start”这条规律。组合总和 II 同理排序后循环里加一句 if (i start nums[i] nums[i-1]) continue; 就能去重。很多时候你会发现面试官出题是一串的先问全排列再问子集再问组合总和。如果你能把这三题的代码放一起对比着看去重逻辑会形成肌肉记忆。6.2 面试延伸与复习建议面试官在这道题上的追问点我总结下来主要是四个去重条件为什么是 !used[i-1]为什么先排序不排序怎么做复杂度是多少。第一个问题我在前文已经拆解得很细了这里不再重复。不排序方案我也讲了就是每层新建 Set。面试时如果被问到你可以先说“排序 相邻剪枝”是最常见的方案再补充一句“也可以用每层的 HashSet两种都能过”。这样既展示了知识面又体现了你理解两种方案的取舍。最后聊点我个人的经验。我第一次刷这题时也是被 !used[i-1] 这个条件折磨了很久后来发现与其死记硬背不如亲手画一棵递归树。刷回溯专题笔和纸比任何神器都管用。现在每次遇到去重相关的回溯题我都会条件反射地先想清楚一个问题我到底要剪“同一层”还是“同一路径”想明白了这一层代码基本不会写错LeetCode 47 也就真正吃透了。