2019-05-24LeetCode90. 子集 II

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # 避免[4,1,4]最后的结果[1,4][4,1]的重复
        t,res=len(nums),set()
        for i in range(1<<t):
            tmp,line=[],0
            for j in range(t):
                if i&(1<<j):
                    c=nums[j]
                    tmp.append(c)
                    line+=c
            res.add(tuple(tmp))  #之所以要这么麻烦是因为list可变无法hash
        re=[]
        for i in res:
            re.append(list(i))  #将tuple转化为list
        return re

思考方法当然先排序，然后如果不重复那自然简单的把原先的子集扩充一倍，如果重复的话，由于地位和重复的数字一样，就只能加入原先包括重复数字的子集中

class Solution2:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res=[[]]
        for i in range(len(nums)):
            if(i==0 or nums[i]!=nums[i-1]):
                l=len(res)
                for t in range(len(res)):
                    res.append(res[t]+[nums[i]])
            else:
                p=len(res)
                for t in range(l,len(res)):
                    res.append(res[t]+[nums[i]])
                l=p
        return res
``
参考如下代码但是真的写不出啊臣妾，其中难以理解的主要是l，l表示最后一次不等的时候生成了多少新的子集。比如[1,2,2,2]  [[],[1],[2],[1,2]], 此时l=2，以后每次生成2个新的子集。

class Solution3:
# @param num, a list of integer
# @return a list of lists of integer
def subsetsWithDup(self, S):
res = [[]]
S.sort()
for i in range(len(S)):
if i == 0 or S[i] != S[i - 1]:
l = len(res)
for j in range(len(res) - l, len(res)):
res.append(res[j] + [S[i]])
return res