回溯算法--LC47.全排列II

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 相较于46，此时数组里面又重复的数字，此时要考虑去重
        # 去重一定要先排序
        path = list()
        result = list()
        # 去重一定要先排序，一定要先排序
        nums.sort()
        used = [0 for _ in range(len(nums))]
        def backtracking(nums):
            if len(path) == len(nums):
                result.append(path[:])
                return
            for i in range(0, len(nums)):
                if not used[i]:
                    # 去重一定要先排序，排序后这里的条件才有用
                    if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                        continue
                    used[i] = 1
                    path.append(nums[i])
                    backtracking(nums)
                    path.pop()
                    used[i] = 0
        backtracking(nums)
        return result