[DFS]90. Subsets II

• 分类：DFS
• 时间复杂度: O(n^2)
• 空间复杂度: O(n^2)

90. 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:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

代码：

第一遍代码：

class Solution:
    def subsetsWithDup(self, nums: 'List[int]') -> 'List[List[int]]':
        
        res=[]
        if nums==None or len(nums)==0:
            return res
        
        nums.sort()
        visited=[0 for i in range(len(nums))]
        for k in range(len(nums)+1):
            self.dfs(0,k,res,nums,[],visited)
        
        return res
    
    def dfs(self,start,k,res,nums,mylist,visited):
        
        if k==0:
            res.append(mylist.copy())
            return 
        
        for i in range(start,len(nums)):
            
            if i>0 and visited[i-1]==0 and nums[i]==nums[i-1]:
                continue
            mylist.append(nums[i])
            visited[i]=1
            self.dfs(i+1,k-1,res,nums,mylist,visited)
            mylist.pop()
            visited[i]=0

第二遍代码：

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res=[]
        if nums==None or len(nums)==0:
            return res
        nums.sort()
        self.dfsHelper(nums,0,[],res)
        return res
        
    def dfsHelper(self,nums,index,subset,res):
        res.append(subset.copy())
        for i in range(index,len(nums)):
            if i>0 and nums[i]==nums[i-1] and i>index:
                continue
            subset.append(nums[i])
            self.dfsHelper(nums,i+1,subset,res)
            subset.pop()

讨论：

1.这道题是subset1和duplicated题目的结合体
2.去除duplicated的题目首先都是要先排序，然后再前面一个没被visit，但是后面那个和前面那个一样的时候就不要了。

3. 第二遍写这个题是用九章算法的思路，这里i>index，其实和visit一样，不过虽然省了空间，但是会让人有点想不明白。这里就是这里这个数和上一个数一样，并且index==最开始那个i-1，就是visit过了，就过。有点选代表的思路。