90.子集II

backtracking, https://leetcode.cn/problems/subsets-ii/

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

数组的子集是数组中选择一些元素（可能为空）。

解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

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

python

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = set()
        def dfs(i, path):
            if i == n:
                ans.add(tuple(path))
                return 
            
            dfs(i+1, path + [nums[i]])
            dfs(i+1, path)
        
        dfs(0, [])
        return list(ans)

考虑数组 [1,2,2]，选择前两个数，或者第一、三个数，都会得到相同的子集。

也就是说，对于当前选择的数 x，若前面有与其相同的数 y，且没有选择 y，此时包含 x 的子集，必然会出现在包含 y 的所有子集中。可以通过判断这种情况，来避免生成重复的子集。

python

from typing import List

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # 对输入数组进行排序
        result = []

        def backtrack(start=0, current=[]):
            # 将当前构建的子集添加到结果集中
            result.append(current[:])
            for i in range(start, len(nums)):
                # 如果当前元素与前一个元素相同，则跳过，避免重复子集
                # i > start 确保只跳过当前层的重复元素，而不会影响递归中更深层的重复元素
                if i > start and nums[i] == nums[i-1]:
                    continue
                # 做选择
                current.append(nums[i])
                # 递归调用，继续构建子集
                backtrack(i + 1, current)
                # 撤销选择
                current.pop()
        
        backtrack()
        return result

90.子集II ​

90.子集II