题解 | #有重复项数字的全排列#

思路：在题目BM55，没有重复项数字的全排列的做法上做减枝操作。

• num排序，使得重复数字邻近；
• 去重：当前arr以外的数字中，选择重复数字的第一个做递归，其余的重复项跳过

  import copy
  class Solution:
      res = []
      def permuteUnique(self , num: List[int]) -> List[List[int]]:
          num.sort()
          mark = [0 for i in range(len(num))]
          arr = []
          self.full_permute(num,arr,mark)
          return Solution.res
      
      def full_permute(self, num, arr, mark):
          if len(arr) == len(num):
              # res.append()添加的是arr的引用，递归结束后，arr==[]，res会全为空
              # 因此需要在新内存中复制一份当前的arr
              Solution.res.append(copy.deepcopy(arr))
          for i in range(len(num)):
              # mark[i]==1，表示已在arr中，跳过
              # i>0 and num[i]==num[i-1]，当前数字不是重复项的第一个(i>0避免越界)
              # mark[i-1]==0，num[i-1]是arr以外的数
              if mark[i]==1 or i>0 and num[i]==num[i-1] and mark[i-1]==0:
                  continue
              arr.append(num[i])
              mark[i] = 1
              self.full_permute(num,arr,mark)
              arr.pop()
              mark[i] = 0