Subset

Question

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],
  []
]

Note Each element in a subset must be in non-descending order.

The ordering between two subsets is free.

The solution set must not contain duplicate subsets.

Thoughts

先sort就可以在连续相同的元素时只使用一个，就可以避免重复的subset

Solution

class Solution:
    """
    @param S: A set of numbers.
    @return: A list of lists. All valid subsets.
    """
    def subsetsWithDup(self, S):
        # write your code here
        self.resultList = []
        self.S = S
        self.S.sort()
        self.subsetsHelper([], 0)
        return self.resultList

    def subsetsHelper(self, curList, pos):
        newList = list(curList)
        self.resultList.append(newList)

        for i in range(pos, len(self.S)):
            if i != pos and self.S[i-1] == self.S[i]:
                continue
            curList.append(self.S[i])
            self.subsetsHelper(curList, i + 1)
            curList.pop()