卖萌的弱渣

I am stupid, I am hungry.

Subsets II

Given a list of numbers that may has duplicate numbers, return all possible subsets

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.

Example

If S = [1,2,2], a solution is:

1
2
3
4
5
6
7
8

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

Solution

  • Use DFS to solve the problem.
  • enumerate is useful.
(Subsets2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    """
    @param S: A set of numbers.
    @return: A list of lists. All valid subsets.
    """
    def subset_helper(self,numbers,solution,result):
        # insert get one solution
        result.append(solution[:])
        for i,en in enumerate(numbers):
            # remove duplicated cases
            if i >0 and numbers[i] == numbers[i-1]:
                continue

            solution.append(en)
            # cut the dfs
            self.subset_helper(numbers[i+1:],solution,result)
            solution.pop()
        return


    def subsetsWithDup(self, S):
        # write your code here
        result = []
        self.subset_helper(sorted(S),[],result)
        return result

if __name__ == "__main__":
    sol = Solution()
    print(sol.subsetsWithDup([0]))