Subsets ii

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()