47. 全排列 II

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

思路：

• 回溯，确定出口，path长度为len(nums)的时候出去
• 维护一个check列表，表示该数是否被使用了
• 剪枝策略：
  • 如果该数被使用了，跳过该数，剪枝
  • nums排序，如果后一个数和前一个数相同，且，前一个数没有使用的时候，跳过这个数，剪枝

PS：path+[nums[i]]也可以这样写 path.append(nums[i]) backtracking() path.pop()

可以理解为，只把扩展后的path传入了递归，其本身没有改变，相当于加进去了又pop了

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        check = [0 for _ in range(len(nums))]
        def backtracking(path):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if check[i] == 1: continue
                if i > 0 and nums[i] == nums[i-1] and check[i-1] == 0: continue
                check[i] = 1
                backtracking(path + [nums[i]])
                check[i] = 0

        backtracking([])
        return res