90.subset_ii.md

90. Subsets II

中等

https://leetcode-cn.com/problems/subsets-ii/

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10

相关企业

• Facebook|4
• 字节跳动|2
• 亚马逊 Amazon|2
• 彭博 Bloomberg|2

相关标签

• Bit Manipulation
• Array
• Backtracking

idea

Ask find all subsets -> find all possible solution /all plans problem -> DFS

sol DFS recursion + remove duplicate 去重

• 1. find all solutions and then remove duplicate
  • high time complexity
  • like [1,1,1,1,1] : O(2^n)
• 2. remove duplicate during searching (this is better)

复杂度分析

• 时间复杂度： O ( n ∗ 2^ n ) ，其中n为nums的长度。生成所有子集，并复制到输出集合中。
• 空间复杂度： O ( n ∗ 2^ n ) ，其中n为nums的长度。存储所有子集，共 n个元素，每个元素都有可能存在或者不存在。

去重 remove duplicate - 选代表

[1, 2', 2'']

• [1, 2'] 选这个做代表。有序好处理
• [1, 2'']

[1, 2, 3]

• [1, 2, 3] 选这个做代表。有序好处理
• [2, 1, 3]
• [3, 1, 2]
• ...

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []
        
        nums = sorted(nums) # must sort so that to remove duplicate later
        results = []
        self.dfs(nums, 0, [], results)
        return results
    
    # 1. recursion definition: find all subsets starting with nums[startIndex]
    def dfs(self, nums, startIndex, curr_subset, results):
        # 2. recursion divide
        # deep copy
        results.append(list(curr_subset))

        # next recursion level 
        for i in range(startIndex, len(nums)):
            # different than 78.subsets
            if i > 0 and nums[i] == nums[i - 1] and i > startIndex:
                continue # duplicate element
            curr_subset.append(nums[i])
            self.dfs(nums, i + 1, curr_subset, results)
            curr_subset.remove(nums[i]) # backtracking

        # 3. recursion stopping
        return

去重 remove duplicate - hash (python: set or dict)

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []
        
        nums = sorted(nums) # must sort so that to remove duplicate later
        results = []
        visited = set()
        self.dfs(nums, 0, [], results, visited)
        return results

    def get_hash(self, curr_subset):
        hash_string = "-".join([str(num) for num in curr_subset])
        return hash_string
    
    # 1. recursion definition: find all subsets starting with nums[startIndex]
    def dfs(self, nums, startIndex, curr_subset, results, visited):
        # avoid duplicate
        hash_string = self.get_hash(curr_subset)
        if hash_string in visited:
            return

        # 2. recursion divide
        # deep copy
        results.append(list(curr_subset))
        visited.add(self.get_hash(curr_subset))

        # next recursion level 
        for i in range(startIndex, len(nums)):
            curr_subset.append(nums[i])
            self.dfs(nums, i + 1, curr_subset, results, visited)
            curr_subset.remove(nums[i]) # backtracking

        # 3. recursion stopping
        return