LeetCode_Subsets II

Posted on | In | Views:

Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
（列举所有子集）

Note: The solution set must not contain duplicate subsets.

Example:



1. 回溯法 / DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def dfs(self, index, re):
        if sorted(re) not in self.results:
            self.results.append(sorted(re))

        for i in range(index, len(self.nums)):
            self.dfs(i+1, re)
            self.dfs(i+1, re + [self.nums[i]])
            
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        self.results = []
        self.nums = nums
        self.dfs(0, [])
        
        return self.results