这道题我第一次遇到的时候心里想的是“全排列 I 都写熟了加个去重能有多难”结果真上手才发现难的不是写代码而是搞清楚那两行剪枝条件背后的状态关系。Permutations II 的核心就一句话输入数组里可能包含重复数字要求输出所有互不相同的排列。它和普通全排列的区别听起来只是加了一步去重但这一步直接把回溯算法从“机械枚举”推到了“理解等价状态”的层次。这篇文章就是用来掰开揉碎讲清楚为什么要排序、为什么要 used 数组、那个!used[i-1]到底是干什么的以及你把这套模板搬到子集、组合问题的时候要怎么变通。不管你是准备算法面试、刷题做总结还是第一次接触回溯去重这篇都能给你一套能直接复用的思考方式和代码模板。1. 题面复盘从全排列 I 到全排列 II 的质变1.1 重复数字到底给问题加了什么难度先看两个例子。[1,2,3]的全排列有 6 个每个元素互不相同枚举出来天然没有重复。但如果是[1,1,2]计算机面对的不是两个1和 一个2而是下标 0 的1、下标 1 的1、下标 2 的2。在朴素回溯里下标 0 和下标 1 会被当成两个不同的候选于是你会得到两个看起来一模一样的[1,1,2]。换句话说重复的本质不是数值重复而是不同的下标路径产生了等价的排列结果。题目不关心你是用了哪个 1它只关心最终的排列序列长什么样。所以这道题要做的是把“下标维度”收敛到“值维度”对于数值相同的元素它们在同一位置的“出场身份”是等价的只保留一种即可。这一点想通了后面的剪枝代码就顺理成章了。1.2 直接在结果集合里用 Set 去重为什么是下策很多初学者第一反应是先按全排列 I 生成所有排列最后塞进一个SetListInteger把重复项丢掉。这个方案确实能过但我不推荐用它作为主要解法原因有三条。第一生成阶段没有剪枝递归树会白白长出大量重复分支。比如输入是[1,1,1,1,1,1,1,1,1]实际答案只有一个[1,1,...]但朴素回溯会走 9! 条路径每一条都在构造一个注定要被丢弃的排列。时间浪费极其夸张。第二空间峰值翻倍。你得把所有原始排列都存下来再靠 Set 去重内存开销远高于边生成边剪枝的方案。第三也是最要命的面试官想看的是你在递归过程中理解“等价状态”并提前剪枝而不是事后清洗数据。回溯专题的核心思想就是“在决策树的生长过程中做减法”你如果依赖 Set反而暴露了对剪枝逻辑的陌生。所以真正工程化、也真正符合面试导向的做法是在枚举的过程中砍掉重复分支。2. 回溯框架与状态设计2.1 回溯三要素路径、选择列表、终止条件先复习一下回溯的通用骨架后面所有代码都建立在它上面。路径path当前已经选好的元素顺序。选择列表本次递归还能选哪些元素。对排列问题来说选择列表是“还没用过的下标”。终止条件path.length n说明一条完整排列已经生成。每次递归往下走一层就相当于在决策树上更深了一步返回当前层时必须撤销刚才的选择恢复现场让循环里的下一个分支能正常探索。这就是“回溯”这个名字的由来。全排列 I 的模板长这样def permute(nums): n len(nums) used [False] * n res [] path [] def dfs(): if len(path) n: res.append(path[:]) return for i in range(n): if used[i]: continue used[i] True path.append(nums[i]) dfs() path.pop() used[i] False dfs() return res这里的used数组解决的是“每个下标只能用一次”的约束。2.2 排序 used 数组把重复元素变成相邻到了全排列 II我们要在模板上加一个去重机制。第一步通常是排序。排序本身不是排列逻辑必需的它只是为了方便检测重复两个相同的值在排序后一定相邻。这样遍历选择列表时你只需要回头看前一个元素是不是和自己相等就能知道当前候选是不是有可能产生重复分支。但注意不能只判断nums[i] nums[i-1]就直接剪掉。因为前一个相同值此时可能已经被当前排列选中了它还躺在path里这种情况下当前这个重复值是该被允许使用的。举个例子[1,1,2]第一层选了下标 0 的 1第二层必须还能选下标 1 的 1否则永远拼不出[1,1,2]这个结果。所以去重剪枝必须结合used[i-1]的状态一起判断。2.3 核心剪枝条件逐行拆解完整的去重剪枝长这样if i 0 and nums[i] nums[i-1] and not used[i-1]: continue三个条件缺一不可。i 0保证访问nums[i-1]时下标不越界。nums[i] nums[i-1]发现相邻重复值。not used[i-1]前一个相同值没有进入当前路径。为什么是“前一个相同值不在当前路径时”才剪枝因为当used[i-1]为 False说明前一个重复值代表的分支已经完整探索完并恢复了现场现在轮到当前这个下标了。此时从下标 i 开始选生成的排列会和从下标 i-1 开始时逐位完全相同没有任何新的可能性必须跳过。反过来当used[i-1]为 True说明前一个重复值已经因为某个更靠前的位置被选中而进入了路径。这种场景下当前重复值就是“补充位”是合法且必需的。如果这时候还剪枝就会出现漏解。可以用一个生活化的类比帮助记忆假设一排替补队员编号相同一个已经被派上场了你再从候补席调一个同编号的人上场合情合理但如果前面那个人还在替补席没动你直接点后面那个同编号的人上场产生的效果和点前面那个人上场完全一样没必要。2.4 一个辅助视角把重复值“排好队”再换一个理解角度你可以规定所有数值相同的元素只能按照数组顺序、按下标升序依次进入路径。这样后来者永远需要检查一个问题——“我的前一位同值队友是不是已经进队了”。前一位还没进队说明你现在插队了剪掉。前一位已经进队说明你按顺序轮到了合法。这种“排队入列”的规则天然把同一组重复元素的不同排列顺序收敛成一种。很多人读到别的题解时会发现去重条件写的是if (used[i-1]) continue那就是“排队入列”视角下的另一种写法。它也能得到正确结果但逻辑表述不如not used[i-1]直观。我建议初学者统一使用not used[i-1]版本因为它直接对应“同一层不能重复选择相同值”的直觉后面讲子集问题时也更好迁移。3. 代码实现与复杂度分析3.1 Python 实现最直白的模板下面是最常用的 Python 写法建议直接背诵理解每一行的作用再刷下一道题def permuteUnique(nums): n len(nums) nums.sort() used [False] * n res [] path [] def dfs(): 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]) dfs() path.pop() used[i] False dfs() return res几个关键细节path[:]必须拷贝。如果不拷贝最终res里的所有列表都会指向同一个对象回溯结束时它们会全部变成空列表这是回溯题最经典的翻车点之一。排序放在dfs之前。整个过程排序一次就够了不要在递归里反复排序。used[i]判断和去重剪枝的顺序无所谓只要两个条件都判断到就行。3.2 Java 版本与易错点补充Java 写法和 Python 思路完全一致只是语法更啰嗦public ListListInteger permuteUnique(int[] nums) { Arrays.sort(nums); ListListInteger res new ArrayList(); DequeInteger path new ArrayDeque(); boolean[] used new boolean[nums.length]; dfs(nums, used, path, res); return res; } private void dfs(int[] nums, boolean[] used, DequeInteger path, ListListInteger res) { 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.addLast(nums[i]); dfs(nums, used, path, res); path.removeLast(); used[i] false; } }易错点主要有三个一是 Java 里List是引用类型加入结果集时必须new ArrayList(path)二是回溯删除末尾元素时别删成头部三是ArrayDeque做栈或队列用没问题但如果要按下标访问直接用ArrayList更顺手。C 版本的核心结构类似只是用vector和pop_back()这里不展开写完整代码理解了状态机就没差别。3.3 时间复杂度是怎么推出来的时间复杂度的推导要看两个层面。无重复时排列数是n!每个排列生成后拷贝一次需要 O(n) 的时间所以总工作量是 O(n · n!)。有重复时实际输出排列数为n! / (c1! · c2! · ...)其中 ck 是每种数字的出现次数。剪枝会砍掉大量重复分支实际生成的节点数更接近这个数乘以 n开销会显著下降。但最坏情况仍然是无重复输入复杂度上界是 O(n · n!)。空间复杂度方面递归深度最大为 n加上used和path各 O(n)辅助空间是 O(n)结果集本身不算在额外辅助空间里。3.4 重要辨析!used[i-1]与used[i-1]两种写法网上很多题解里剪枝条件会看到两种形式# 写法 A推荐 if i 0 and nums[i] nums[i-1] and not used[i-1]: continue # 写法 B if i 0 and nums[i] nums[i-1] and used[i-1]: continue两种写法都能去重但它们代表两种不同的视角。写法 A 的语义是“同一层的重复值只需要第一个代表后面的跳过”它把重复分支扼杀在选择之前。写法 B 的语义是“同值元素必须按下标升序进入路径插队者剪掉”它把重复组内部的相对顺序固定死。从结果上看两者都输出正确集合。但写法 B 容易让人误以为“前一个同值被用过就应该剪”导致在解释代码时卡壳。所以我的建议很简单记住写法 A不要混用。如果面试官追问另一种写法你再把“排队入列”的视角讲给他听。4. 延伸同一个去重模板搬到哪里都能用4.1 子集 II 与组合总和 II同一套剪枝搬到哪都能用排列、子集、组合是回溯里最常被放在一起比较的三大类型。去重思路高度统一排序然后保证同一层递归不取相同值。子集 II 是另一个经典题。给定[1,2,2]要求输出所有不重复子集。代码模板是def subsetsWithDup(nums): nums.sort() res [] path [] def dfs(start): res.append(path[:]) for i in range(start, len(nums)): if i start and nums[i] nums[i-1]: continue path.append(nums[i]) dfs(i 1) path.pop() dfs(0) return res注意这里去重条件是i start而不是i 0。因为子集和组合是从start开始往后选的同一层递归里只要当前位置之前已经取过一个相同的值后面的同名值就直接跳过。组合总和 II 本质一样只不过收集条件是sum target终止逻辑稍微变一下。三种问题放在一起记会形成一张完整的知识网。4.2 排列 / 子集 / 组合的去重口诀我把总结成一个口诀方便临时记忆排列加 used组合子集靠 start排序是前提重复看层内。具体来说排列问题每层都要从 0 开始扫描用used防止同一元素重复使用去重条件是used[i-1]为假时跳过。组合/子集问题每层从start开始扫描靠start天然避免组合重复去重条件是i start时跳过同值。另一个容易混淆的点排列每次递归都要for i in range(n)因为不同的排列顺序意味着完全不同的结果而组合/子集只用for i in range(start, n)否则会出现[1,2]和[2,1]这种顺序不同但组合相同的结果。如果题目改成字符串排列比如输入aab把字符串转成字符数组后排序逻辑完全一致。无非是把nums[i]换成chars[i]。4.3 为什么不建议用 HashSet 全局去重再补充一个理由前面讲过全局去重在效率和空间上的问题还有一个隐藏缺陷它会破坏字典序输出。很多扩展题要求按字典序从小到大输出所有排列或者要求你返回第 k 个排列。如果你依赖 Set 事后去重生成的中间顺序已经乱掉了还得额外排序非常被动。而剪枝方案在排完序之后递归自然按照字典序生成结果。这个特点在面试里经常被追问提前意识到这一点你能比只背模板的候选人多展示一层理解。5. 常见问题与排查技巧实录5.1 问题一结果集里还是出现重复排列如果输出里残留重复排列九成是下面两种情况。第一种忘了排序。nums[i] nums[i-1]只能检测相邻重复不排序的话相同值的下标可能隔得很远根本检测不到。第二种剪枝条件写错。最常见的是漏写not used[i-1]把它写成了if i 0 and nums[i] nums[i-1]: continue这个错误很隐蔽因为它通常表现为漏解而不是重复。以[1,1,2]为例第一层循环到i 1时nums[1] nums[0]直接 continue第二个 1 在这一层永远不会被选可第二层其实需要它能被选于是[1,1,2]压根生成不出来。排查技巧在 continue 之前打一行日志打印当前i、used数组和path对照[1,1,2]的递归树看剪枝是否合理。5.2 问题二剪枝过于激进结果集少了另一种常见情况是把剪枝写成used[i-1] True时跳过。之前说过这种写法思路是“同值元素按下标顺序入队”本身没问题。但问题在于如果你没有把整个逻辑统一成“排队入列”而是跟默认模板混在一起就会出现某些分支允许了插队、某些分支又禁止了逻辑混乱后很难调试。我的建议是初学者只用not used[i-1]版本。等你能独立把手写样例跑通、闭着眼画出[1,1,2]的递归树之后再去看另一种写法也不迟。5.3 问题三内存和运行时间表现很差性能差的根源几乎都是“重复分支没剪干净”。输入重复元素越多不剪枝的代价越恐怖。哪怕输入只有 10 个元素其中 9 个相同朴素回溯要跑 10! 次而剪枝后实际结果只有 10 个排列差距是数量级的。如果面试官让你继续优化可以提迭代式的下一个排列法先排序每次调用 nextPermutation 生成字典序更大的排列直到回到最初状态。这个过程天然只会枚举去重后的排列不会产生任何重复分支空间复杂度还能压到 O(1)。缺点是代码比回溯长且需要先理解字典序排列的调整逻辑一般作为扩展方案交代即可。另一个常见误区是在递归内部频繁创建HashMap之类的计数结构。完全没必要排序 used 数组已经是最节省的辅助结构了。5.4 调试必备手动展开递归树我强烈建议你遇到回溯题先手动画树尤其是[1,1,2]这种小用例。展开是这样的根节点第一层尝试nums[0]1进入第二层。第二层尝试nums[1]1此时used[0]Truei1虽然nums[1]nums[0]但used[0]为真不剪枝路径变成[1,1]第三层只能选 2得到[1,1,2]。第二层再尝试nums[2]2第三层选剩余的nums[1]1得到[1,2,1]。根节点第一层再尝试nums[1]1此时nums[0]1还未被使用used[0]False剪枝拦截避免生成与上面分支重复的排列。根节点第一层尝试nums[2]2第二层选nums[0]1第三层选nums[1]1得到[2,1,1]第二层如果先选nums[1]1则因为used[0]False被剪掉。这张树画完!used[i-1]的本质就彻底清楚了。它不是在阻止重复元素“连续出现”而是在阻止“同一层出现两个相同起点”。6. 面试场景与实用建议6.1 面试官在这道题上真正想考察什么这道题在面试里的地位很高因为它同时考察了好几层能力。第一层识别等价状态。你能不能看出“两个相同数值的下标在当前层是等价的”决定了你会不会写出used[i-1]剪枝。第二层区分层内去重与分支间去重。排列和组合的去重条件长得像但完全不同能讲清楚的人才是真的理解了回溯状态。第三层边界处理能力。i 0防越界、path[:]防引用污染、递归结束后恢复现场这些都是写代码的硬功夫。面试里的高频追问我也整理一下不排序能去重吗可以用哈希表统计每个值的剩余次数遍历哈希表的 key 而不是数组下标。要求按字典序输出怎么办排序后递归天然输出字典序。全重复输入会怎样剪枝后只输出一个排列性能依旧稳定。6.2 我的个人建议与笔记技巧如果你也在准备这一类回溯题我的建议是不要背代码背“剪枝认知表”。判定三件套排序、used 数组、i0 nums[i]nums[i-1] !used[i-1]。一句话记忆同值不同下标一次决策一个代表。把全排列 II、子集 II、组合总和 II 放同一批刷。我的笔记会把三个模板并排写在一页纸上每次只对比“循环起点”和“去重条件”两列很快就能建立起完整的回溯去重体系。我自己刷这道题时踩过最深的坑是以为!used[i-1]的意思是“只要前面没用过就跳过”结果把整个逻辑理解反了。后来手画递归树才醒悟它的真实作用是对“同一层已经出现过的数值选项”做拦截。如果你也卡在这里不妨也拿出一张纸把[1,1,2]的递归树画出来边画边想为什么第二层选第二个 1 是合法的。画完那一瞬间这道题就真正拿下了。