0090. Subsets II.md

• 90 - Subsets II
• 难度：Medium｜ 中等
• 相关知识点：Array | Backtracking | Bit Manipulation
• 题目链接：https://leetcode.com/problems/subsets-ii/description/

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

solution 1 回溯

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        nums.sort()
        for i in range(len(nums)):
            if i >= 1 and nums[i] == nums[i - 1]:
                new_subsets = [subset + [nums[i]] for subset in new_subsets]
            else:
                new_subsets = [subset + [nums[i]] for subset in res]
            res = new_subsets + res
        return res

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result =[[]]
        start = 0
        last = 0

        for i in range(len(nums)):
            if not (i-1 >= 0 and nums[i] == nums[i-1]):
                start = 0
            else:
                start = last
            last = len(result)
            result += [r +[nums[i]] for r in result[start:]]

        return result

上面版本的变形：

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
       nums.sort()
       result = [[]]
       start = 0
       
       for i in range(len(nums)):
           if i > 0 and nums[i] == nums[i-1]:
               start = len(result)
           else:
               start = 0
           
           for j in range(start, len(result)):
               result.append(result[j] + [nums[i]])
   
       return result

solution 2 迭代

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start, ans):
            result.append(ans[:])
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                backtrack(i+1, ans + [nums[i]])
    
        result = []
        nums.sort()
        backtrack(0, [])
        return result

solution 3 位运算

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        n = len(nums)
    
        for i in range(1 << n):
            subset = []
            skip = False
    
            for j in range(n):
                if i & (1 << j):
                    # 判断是否是重复元素，如果是，则跳过该状态
                    if j > 0 and nums[j] == nums[j-1] and not (i & (1 << (j-1))):
                        skip = True
                        break
                    subset.append(nums[j])
    
            if not skip:
                result.append(subset)
    
        return result

• i & (1 << j) 用于检查当前子集状态 i 中的第 j 个元素是否被选中

• (i & (1 << (j-1))) 确定前一个元素是否被选中