47：全排列 II

问题描述

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

示例

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

写在做题之前

hash良好的查找性能是建立在良好的hash算法上的，我们需要有好的散列函数和冲突处理机制，所以我们所说的O(1)只是说hash查找的量级是O(1)，并不是说我们就可以不需要计算了。
所以如果我们查找用的是数组的index进行查找的话，性能是比hash要高一点点的。

思路

这题与之前几道题类似的做法，都是回溯法+剪枝。问题是怎么剪枝。
对于这个题目，我们只能用curs数组的长度来判定是否结束递归。这题的另外一个约束条件是，不能重复。所以说我们要剪枝。什么情况下剪枝呢？
我们发现对于112来说。 待选序列是112， 会产生重复的112.
如果对于122来说，选了1之后，待选序列是22，会产生重复的122.
所以说，只要待选序列有连续的相同数字，就要剪枝。

看大神的图片：

AC代码：

class Solution:
    def permuteUnique(self, nums):
        res = []
        nums.sort()
        right = len(nums)
        # used = set() # 标记已经用过的元素
        used = [False] * len(nums)
        def solution(nums,right,curs,used):
            if len(curs) == right:
                res.append(curs[:])
            for i in range(right):
                if not used[i]:
                    if i > 0 and nums[i-1] == nums[i] and not used[i-1]:
                        continue
                    used[i] = True
                    curs.append(nums[i])
                    solution(nums,right,curs,used)
                    used[i] = False
                    curs.pop() # 状态回退
        solution(nums,right,[],used)
        return res
s = Solution()
print(s.permuteUnique([1,2,2]))