原題
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],
[]
]
注意點
- 集合中包含重復的數(shù)字需要按照升序排列
- 結果集中不能含有重復子集
思路
該題和Subset題目相似蹭睡，只是加上了重復數(shù)字善炫。
解法思路有兩種：
1勒叠、使用Python內(nèi)置庫，和Subset題目用法相似职抡。
2葬燎、在迭代集合元素時需要對重復元素特殊處理。比如[1, 2, 2]集合，迭代完第一個2時,
結果集中是[[], [1], [2], [1, 2]], 如果再迭代第二個2時就會產(chǎn)生重復的子集([2], [1, 2]),
所以需要對從上次迭代產(chǎn)生的新的子集里面進行迭代谱净，可以通過添加一個變量來標記結果集的起點窑邦，
也就是第二個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
