题目描述
思路解析动画文字版
记住这条去重判断「同层、相同值、前一个没用就跳过」,下面每一帧都在套它。
开局:nums 已排好序 [1,1,2],path 是空的,三个数都没用过(白色),结果 res 也是空。每一层从头扫候选,挑一个没用过的放进 path——但碰到重复值要小心。
选中没用过的 1(第 0 个):标记它为已用、放进 path。现在 path = [1],往下一层递归。
这一层从头扫:第 0 个数 1 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
选中没用过的 1(第 1 个):标记它为已用、放进 path。现在 path = [1,1],往下一层递归。
这一层从头扫:第 0 个数 1 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
这一层从头扫:第 1 个数 1 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
选中没用过的 2(第 2 个):标记它为已用、放进 path。现在 path = [1,1,2],往下一层递归。
path 凑满了 3 个数 —— 记下这个排列 [1,1,2]。然后开始往回退(回溯),去试别的可能。
回溯:把第 2 个的 2 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
回溯:把第 1 个的 1 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
选中没用过的 2(第 2 个):标记它为已用、放进 path。现在 path = [1,2],往下一层递归。
这一层从头扫:第 0 个数 1 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
选中没用过的 1(第 1 个):标记它为已用、放进 path。现在 path = [1,2,1],往下一层递归。
path 凑满了 3 个数 —— 记下这个排列 [1,2,1]。然后开始往回退(回溯),去试别的可能。
回溯:把第 1 个的 1 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
这一层从头扫:第 2 个数 2 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
回溯:把第 2 个的 2 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
回溯:把第 0 个的 1 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
去重剪枝:第 1 个数 1 和它前面那个相等(都是 1),而前一个这层没用(白色)——说明前一个等值数刚在本层试过又撤销了,再选这个会排出一模一样的排列。打 ✗ 跳过。
选中没用过的 2(第 2 个):标记它为已用、放进 path。现在 path = [2],往下一层递归。
选中没用过的 1(第 0 个):标记它为已用、放进 path。现在 path = [2,1],往下一层递归。
这一层从头扫:第 0 个数 1 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
选中没用过的 1(第 1 个):标记它为已用、放进 path。现在 path = [2,1,1],往下一层递归。
path 凑满了 3 个数 —— 记下这个排列 [2,1,1]。然后开始往回退(回溯),去试别的可能。
回溯:把第 1 个的 1 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
这一层从头扫:第 2 个数 2 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
回溯:把第 0 个的 1 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
去重剪枝:第 1 个数 1 和它前面那个相等(都是 1),而前一个这层没用(白色)——说明前一个等值数刚在本层试过又撤销了,再选这个会排出一模一样的排列。打 ✗ 跳过。
这一层从头扫:第 2 个数 2 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
回溯:把第 2 个的 2 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
边界先想清:全相同的数组只有一个排列,去重把其余全部剪掉。
两个高频追问,记住答法。
参考代码
def permuteUnique(nums): nums.sort() # 排序,让相同值相邻 res, n = [], len(nums) used = [False] * n path = [] 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 res复杂度
- 时间：O(n·n!)，最坏(无重复)仍 n! 个排列,每个拷贝 O(n);去重只会更少
- 空间：O(n)，递归深度 + used + path(不计结果)
易错点
面试追问把动画讲成自己的话
追问为什么去重前一定要先排序?
追问!used[i-1] 和 used[i-1] 两种写法都见过,区别?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题