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

思路

枚举每个数放到哪个位置

如何判重或者去重

人为规定相同数字的相对顺序：排列后顺序不变！
若原序列在前，全排列后也在前

dfs(u, start) # u数组索引，start当前可以从哪个位置开始搜
比如第一个1放到位置5，则第二个1只能从位置6开始放

import copy
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # self.nums = nums.sort() # nums.sort()无返回值
        self.nums = sorted(nums)
        self.n = len(nums)
        self.st = [False for i in range(self.n)]
        self.path = ['None' for i in range(self.n)]; self.ans = []

        self.dfs(nums, 0, 0)
        return self.ans

    def dfs(self, nums, u, start): # start表示从哪个位置开始枚举
        if u == self.n:
            self.ans.append(copy.copy(self.path))
            return None
        i = start
        while i < self.n:
         # 枚举可放置的位置
            if not self.st[i]:
                self.st[i] = True
                self.path[i] = copy.copy(self.nums[u])

                # 当前数组位置后面还有数字时并且后面的数字与当前数字相同,start为i+1，只能在后面位置枚举
                if u + 1 < self.n and self.nums[u + 1] == self.nums[u]:
                    self.dfs(self.nums, u + 1, i + 1)
                else: # 若当前数组位置为最后一个数字或者后面数字与前面不同，可从0开始枚举放置
                    self.dfs(self.nums, u + 1, 0)
                # 此处不需要恢复path，因为path每次更新方式是直接覆盖赋值
                self.st[i] = False
            i += 1