47. 全排列 II

https://leetcode-cn.com/problems/permutations-ii/

解法一：回溯

因为有重复数字，所以不能简单用in运算符去重，改用一个布尔数组used，used[i]=True表示该位置已经用过。

回溯之前还应该排序，便于排除重复结果。

此外还需设置一个特殊条件来排除重复结果：used[i] or i-1 >= 0 and nums[i-1] == nums[i] and not used[i-1]

used[i]表示i如果使用了，跳过，很好理解

i-1 >= 0 and nums[i-1] == nums[i] and not used[i-1]表示看前一位，若与当前相等，且前一位未使用过，则跳过。例如对nums=[1,1,1,2]，三个1是重复元素，取的时候应该作为一个整体取，即nums的0，1，2号，否则会出现重复结果。上面条件的限制使得nums[1]只有在nums[0]出现的时候才取，同理nums[2]只有在nums[1]出现的时候才取，因此保证了结果中三个1的取用先后次序为nums的0，1，2号。

注意，not used[i-1]也可以改成used[i-1]，即前一位使用过，则跳过。还是上面的例子，nums[0]出现后，nums[1]取不了，nums[1]出现后，nums[2]取不了，因此三个1的情况只有是先取nums的2号，然后是1号和0号，和上面反过来

两种思路都可行，都是为了保证相同元素作为一个有序整体取用，从而避免重复

[1,1,1,2]的结果为：

[[1,1,1,2],[1,1,2,1],[1,2,1,1],[2,1,1,1]]

可以看出第0和第3组以三个1为整体，第1第2组分别以前两个1和后两个1为整体

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        tmpList = []
        used = [False] * len(nums)    #标记数组
        nums.sort()
        self.backtrack(nums, tmpList, used)
        return self.res
    
    def backtrack(self, nums, tmpList, used):
        if len(tmpList) == len(nums):
            self.res.append(list(tmpList))
        for i in range(len(nums)):
            #注意复杂条件,最后一个可改为used[i-1]
            if used[i] or i-1 >= 0 and nums[i-1] == nums[i] and not used[i-1]:
                continue
            used[i] = True
            self.backtrack(nums, tmpList + [nums[i]], used)
            used[i] = False    #还原现场

另一种思路：

若重复数字1，1，1中有一个（如第二个）被使用了，则下次选择不选第二个1前面的1，只能往后选：

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs(tmp, used):
            if len(tmp) == n:
                res.append(list(tmp))
            else:
                for i in range(n):
                    if used[i]:    #使用过则跳过
                        continue
                    else:    #若未使用过，看i右边是否有相等且使用过的数字
                        j = i
                        while j+1 < n and used[j] == False and nums[j] == nums[j+1]:
                            j += 1
                        if used[j]:    #若有则跳过
                            continue
                    used[i] = True
                    dfs(tmp + [nums[i]], used)
                    used[i] = False
                    
        nums.sort()
        n = len(nums)
        used = [False] * n
        res = []
        dfs([], used)
        return res