leetcode题解90：子集 II

描述

分析

和力扣第78题题解几乎一样，多了一个重复元素的处理，模拟下生成过程，就知道重复元素如何处理了，以[1,2,2]为例，

空集，[]
添加1，[], [1]
2与1不同，继续添加[], [1], [2], [1, 2]
最后一个2与前面2相同，这时如果依然在上一步中的每个子集都添加就重复了，因为[], [1]已经加过2了，所以只需要对上一步新生成的子集添加2就可以，即[2,2], [1,2,2]

从上面的过程可以看出，对于重复元素的添加区别仅在于，需要添加元素的子集的起点；新元素直接从0开始，如果是重复的元素，从上一步添加的新元素位置开始，即上上步的结束位置。

代码

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = [[]]
        start = len(res)
        res.append(res[0] + [nums[0]])
        end = len(res)
        for i in range(1, len(nums)):
            s = start if nums[i] == nums[i-1] else 0
            for j in range(s, end):
                res.append(res[j] + [nums[i]])
            start = end
            end = len(res)
        return res