47 全排列II

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

示例:

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

解法

• Python

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def test(nums,depth,path,used):
            if depth == length:
                res.append(path.copy())
                return

            for i in range(length):
                if not used[i]:
                    if i>0 and nums[i]==nums[i-1] and not used[i-1]:
                        continue
                    used[i] = True
                    path.append(nums[i])
                    test(nums,depth+1,path,used)
                    used[i] = False
                    path.pop()
        nums.sort()
        length = len(nums)
        used = [False for _ in range(len(nums))]
        res = []
        test(nums,0,[],used)
        return res