90、LeetCode之Subsets II 题解

原题

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

注意点

• 集合中包含重复的数字需要按照升序排列
• 结果集中不能含有重复子集

思路

该题和Subset题目相似，只是加上了重复数字。
解法思路有两种：
1、使用Python内置库，和Subset题目用法相似。
2、在迭代集合元素时需要对重复元素特殊处理。比如[1, 2, 2]集合，迭代完第一个2时,
   结果集中是[[], [1], [2], [1, 2]], 如果再迭代第二个2时就会产生重复的子集([2], [1, 2]),
   所以需要对从上次迭代产生的新的子集里面进行迭代，可以通过添加一个变量来标记结果集的起点，
   也就是第二个2从该起点开始迭代。

解法

解法一： 时间消耗：62ms
from itertools import combinations
def subset(nums):
    res = []
    nums.sort()
    for i in xrange(len(nums) + 1):
        temp = combinations(nums, i)
        guo = [list(i) for i in set(temp)]
        res.extend(guo)
    return res
    
解法二： 时间消耗：58ms
def subset(nums):
    res = [[]]
    nums.sort()
    temp = 0
    for i in range(len(nums) + 1):
        start = temp if i >= 1 and nums[i] == nums[i -1] else 0
        temp = len(res)
        for j in range(start, temp):
            res.append(res[j] + [nums[i]])
    return res