Subsets2

题目

给定一个可能具有重复数字的列表，返回其所有可能的子集

注意事项

子集中的每个元素都是非降序的
两个子集间的顺序是无关紧要的
解集中不能包含重复子集

test case

如果 S = [1,2,2]，一个可能的答案为：

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

思路

eg:

{1,2',2''}
取{1,2'} {2',2''} 
不取 {1,2''} {2'',2‘}
"""
重复的数选取第一次出现的,所以只需要在循环中进行处理，对于不取的情况进行跳过。
判断条件就是
数组不越界
前后两个字符相等
当前字符不是一次出现即 不等于startIndex
"""

结果

class Solution:
    """
    @param S: A set of numbers.
    @return: A list of lists. All valid subsets.
    """

    def subsetsWithDup(self, S):
        # write your code here
        result = []
        if (S is None):
            return result

        def subSetsHelper(nums, startIndex, temp_list, ret):
            # 生成新对象
            ret.append([] + temp_list)
            for i in range(startIndex, len(nums)):
                # 先添加,再移除
                # 判断跳过的循环
                if (i != 0 and nums[i] == nums[i - 1] and i != startIndex):
                    continue
                temp_list.append(nums[i])
                subSetsHelper(nums, i + 1, temp_list, ret)
                temp_list.pop()

        S.sort()
        subSetsHelper(S, 0, [], result)
        return result