在46题的基础上添加了剪枝策略

题目

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

考察知识点

回溯算法

核心思想

方法一、在46题的基础上，增加剪枝条件，去掉重复的。

当该节点没有被使用，且该节点和前面节点的数值一样时，这个节点就应该被剪枝跳过。

• 由于要剪枝，所以在回溯之前要排序。

nums.sort()  # 由于要剪枝，所以必须要提前对nums进行排序，让重复的数字排列在一起。
backtrack()  # 开始回溯，初始时used是000。

• 除了判定前后两个数必须相同以外，还要判定当前位置的前面一个位置（ index - 1 ）是否被占用，因为前一个位置在回溯时肯定是先被释放了占用了的，加入 not used[i - 1] 条件，这样的剪枝更彻底。

if index > 0 and nums[index] == nums[index -1] and (used >> (index - 1)) & 1 == 0:  # 为什么要求used[index-1]，因为一般回溯到这里时，前面used[index-1]的占用就被撤销了。所以要对 index - 1 处进行检查。
	continue

8.png

大佬题解

Python版本

方法一的实现

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtrack(path=[], depth=0, used=0):  # 整个回溯函数只包含两个参数，一个是path（记录选择结果），depth（记录还剩多少没有选择）。也可以不用depth，只传递path。通过比较len(path)和len(nums)，判断是否完成寻找。回溯法就是一种深度优先遍历。
            if depth == length:  # 终止条件是寻找深度达到目标深度
                res.append(path[:])  # 由于list是可变对象，因此，这里要用[:]取到具体的值，再append进res中。
                return  # 也可以不用return，不过有return会好一点，后面逻辑在path添加到res之后就不用执行了。

            for index in range(length):  # 遍历所有待添加数
                if (used >> index) & 1 == 0:  # 如果当前数字没有使用，即该位置的二进制值为0
                    if index > 0 and nums[index] == nums[index -1] and (used >> (index - 1)) & 1 == 0:  # 为什么要求used[index-1]，因为一般回溯到这里时，前面used[index-1]的占用就被撤销了。所以要对 index - 1 处进行检查。
                        continue
                    used ^= (1 << index)  # 将该位置的二进制值从0改成1
                    path.append(nums[index])  # 添加到path
                    backtrack(path, depth+1, used)  # 继续递归回溯
                    used ^= (1 << index)  # 将该位置的二进制值从0改成1，完成深度优先遍历（递归回溯）之后，更新选择情况为False代表还未被选择。
                    path.pop()  # 从path中弹出这一轮被选择的数字，以上两步就是在“撤销选择”。

        res = []  # 声明res、length、used等全局变量
        length = len(nums)
        nums.sort()  # 由于要剪枝，所以必须要提前对nums进行排序，让重复的数字排列在一起。
        backtrack()  # 开始回溯，初始时used是000。
        return res

时间复杂度：\(O(N \times N!)\)，这里 N 为数组的长度。
空间复杂度：\(O(N \times N!)\)
执行用时 ：48 ms, 在所有 Python3 提交中击败了94.50%的用户
内存消耗 ：13.8 MB, 在所有 Python3 提交中击败了25.53%的用户