python算法（输入一个包含重复数字的序列返回不重复的全排列）

1、题目描述

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

2、代码详解 

1. 加入 nums[i] == nums[i-1] 判断
2. nums.sort()

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # nums 选择列表，depth深度， path 路径，used 标记数组！，res 结果
        def dfs(nums, size, depth, path, used, res):
            # 结束条件：nums 中的元素全都在 path 中出现
            if depth == size:
                res.append(path[:])  # 需要传递下path的拷贝，否则对path的修改会影响到结果
                return

            for i in range(size):
                # used[i]==False，表示未被用过
                if not used[i]:
                    # （新加判重）剪枝！！！
                    # 如果出现连续重复的字符,跳出for循环（必须操作，用例1,1，不然会输出["1,1","1,1"]）
                    # 加上not used[i-1],这样的剪枝更彻底，不加也能通过
                    if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                        continue
                    # 做选择
                    used[i] = True
                    path.append(nums[i])

                    # 进入下一层决策树
                    dfs(nums, size, depth + 1, path, used, res)

                    # 撤销选择
                    used[i] = False
                    path.pop()

        size = len(nums)
        if len(nums) == 0:
            return []

        # （排序）在搜索之前就对候选数组排序
        # 一旦发现这一支搜索下去可能搜索到重复的元素就停止搜索，这样结果集中不会包含重复元素
        nums.sort()

        used = [False for _ in range(size)]
        res = []
        dfs(nums, size, 0, [], used, res)
        return res

nums = [1,1,2]
s = Solution()
print(s.permuteUnique(nums)) 

本文地址：https://blog.csdn.net/IOT_victor/article/details/107073704