题目描述
思路解析动画文字版
记住这条去重判断「同层、相同值、前一个没用就跳过」,下面每一帧都在套它。
开局: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 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
边界先想清:全相同的数组只有一个排列,去重把其余全部剪掉。
两个高频追问,记住答法。
参考代码
class Solution: def permuteUnique(self, 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(不计结果)