全排列 II （Python）

LeetCode链接

时间复杂度 O(n * n!)
在全排列的基础上加了个重复元素的情况，并且要求结果不能重复

思路：

1. 先对原始列表排序，使得重复元素都靠在一起
2. 之后在全排列的基础上剪枝

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res_list = []
        path = []
        nums_len = len(nums)
        # 一个相同大小的标记数组 来标记某个下标是否被选择过
        selected = [False for _ in range(nums_len)]
        def doit():
            if len(path) == nums_len:
                res_list.append(path[:])
                return
            for i in range(nums_len):
                if not selected[i]:
                    # 因为已经对nums数组排过序了 此时nums[i] == nums[i - 1]表明可能是重复分支
                    # 但此时包含两种情况  以 [1,1,2] 举例
                    # 情况1、第一层选择了 i=0处的1 第二层选择了 i=1处的1 这种情况是正常的 不应当排除
                    # 情况2、第一层选择了 i=1处的1 此时为重复分支 需要跳过
                    # 所以，仅仅判断 nums[i] == nums[i - 1]仍然不够
                    # 借助selected数组 
                    # 情况1 nums[i]虽然和num[i - 1]相等 但是selected[i - 1] is True表明nums[i - 1]是在上一层被选走的 此时num[i]可以被正常选择
                    # 情况2 select[i - 1] is False 表明这就是个重复的情况 应当排除
                    if i > 0 and nums[i] == nums[i - 1] and not selected[i - 1]:
                        continue
                    # 标记选过
                    selected[i] = True
                    # 添加值
                    path.append(nums[i])
                    doit()
                    # 回滚
                    path.pop()
                    selected[i] = False
        # 先排序保证重复元素靠在一起 这样就可以看nums[i] 是否和nums[i - 1] 相等来判断是否重复
        nums.sort()
        doit()
        return res_list