Given a list of numbers that may has duplicate numbers, return all possible subsets
Example
If S = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
这个题的难点在于如何处理去重
如果看到2(2)就直接跳过，那么带有连续2的结果就没有了
正确方法：
当加入2(2)时， 看2(1) 是否使用了，如果使用了，就可以加入2(2)
实现方法：
使用used数组检查2(1)是否存在
或者在这道题，也可以检查当前的2(2)是否是这次循环的第一个元素
如果是第一个元素，就可以直接用了，因为2(1)是已在上一层中使用了
code
class Solution:
"""
@param S: A set of numbers.
@return: A list of lists. All valid subsets.
"""
def subsetsWithDup(self, S):
# write your code here
S.sort() # first thing first !
res = []
self.helper(res, [], S, 0)
return res
def helper(self, res, subset, S, index):
# base
res.append(list(subset))
# divide
for i in range(index, len(S)):
if i != 0 and S[i] == S[i - 1]: # 遇到了2（2）的情况
if i != index: # 因为是不是第一个数在当前循环，所以跳过这个2（2）
continue
subset.append(S[i])
self.helper(res, subset, S, i + 1)
subset.pop()
