题目

90. 子集 II

给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

解题思路

1. 回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        # 1. 首先对数组排序，使相同的元素相邻
        nums.sort()
        res = []  # 存储最终结果
        
        def backtrack(start: int, path: List[int]):
            # 2. 将当前路径加入结果集
            # path[:] 创建一个新的列表，是当前path的浅拷贝
            # 为什么要拷贝？因为path会在后续的回溯过程中被修改
            # 如果直接使用path，那么添加到res中的是path的引用
            # 当path在后续操作中改变时，res中对应的值也会改变
            # 例如：path=[1,2] → res=[[1,2]]
            #      path.pop() → path=[1] → 如果不用拷贝，res会变成[[1]]
            res.append(path[:])
            
            # 3. 从start开始遍历，避免重复选择之前的元素
            for i in range(start, len(nums)):
                # 4. 去重逻辑：跳过同一层重复的元素
                # i > start 确保是在当前层的遍历中
                # nums[i] == nums[i-1] 判断当前元素是否和前一个元素相同
                if i > start and nums[i] == nums[i - 1]:
                    continue
                    
                # 5. 选择当前元素
                path.append(nums[i])
                # 6. 递归到下一层，注意是 i+1 不是 start+1
                backtrack(i + 1, path)
                # 7. 回溯，撤销选择
                path.pop()
        
        # 8. 从空集开始回溯
        backtrack(0, [])
        return res

原理

1. 排序的作用

  • 将数组排序，使相同元素相邻
  • 便于后续去重处理
  • 例如：[4,1,4,4,4] → [1,4,4,4,4]

2. 回溯过程

  • 每个元素都有”选”和”不选”两种状态
  • 通过 start 参数控制选择的起始位置
  • 使用 path 记录当前路径

3. 去重机制

  • 对于重复元素，只在第一次遇到时使用
  • i > start and nums[i] == nums[i-1] 跳过同层重复元素
  • 例如：对于 [1,2,2]
    1
    2
    3
    4
    第一层：[] 可以选择 1,2,2
    选择1后：[1] 可以选择 2,2
    选择第一个2后：[1,2] 可以选择最后一个2
    第一层选择第二个2时跳过，因为和前一个2重复

4. 复杂度分析

  • 时间复杂度：O(n×2^n)，n是数组长度
  • 空间复杂度：O(n)，递归栈的深度

5. 关键点

  1. 必须先排序，这是去重的基础
  2. 使用 path[:] 创建路径副本
  3. 去重条件 i > start 不能省略
  4. 递归时使用 i+1 而不是 start+1