当前位置：首页 > news >正文

leetcode90.子集II：排序与同层去重的回溯优化策略

news 2025/6/4 18:31:34

一、题目深度解析与重复子集问题

题目描述

给定一个可能包含重复元素的整数数组 nums，返回所有不重复的子集（幂集）。解集不能包含重复的子集，且子集可以按任意顺序排列。例如：

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

核心挑战：重复子集的产生与消除

重复原因：数组中存在重复元素时，不同的选择路径可能生成相同子集（如选择第一个2和第二个2产生相同子集）
解决关键：通过排序和回溯时的条件判断，确保相同元素在同一路径中仅被处理一次

二、回溯解法的核心实现与去重逻辑

完整回溯代码实现

class Solution {List<Integer> temp = new LinkedList<>();  // 存储当前子集List<List<Integer>> res = new ArrayList<>();  // 存储所有子集public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);  // 排序是去重的前提backtracking(nums, 0, temp);return res;}public void backtracking(int[] nums, int start, List<Integer> temp) {res.add(new ArrayList<>(temp));  // 收集当前子集（包括空集）if (start >= nums.length) {  // 终止条件：处理完所有元素return;}for (int i = start; i < nums.length; i++) {// 同层去重：当前元素与前一个相同，且前一个未被处理（i > start）if (i > start && nums[i] == nums[i - 1]) {continue;}temp.add(nums[i]);  // 选择当前元素backtracking(nums, i + 1, temp);  // 递归处理后续元素temp.removeLast();  // 回溯：撤销选择}}
}

核心去重代码解析：

if (i > start && nums[i] == nums[i - 1]) {continue;
}

排序前提：Arrays.sort(nums)确保重复元素相邻，为去重提供条件
条件拆解：
1. i > start：当前元素不是当前层的第一个元素（即前一个元素在同一路径中已被处理）
2. nums[i] == nums[i - 1]：当前元素与前一个元素值相同

三、去重逻辑的数学原理与代码实现

1. 同层去重的核心思想

子集生成的两种重复场景：

不同层重复：路径1→2和1→2（同一元素的不同副本，合法，如不同层的2）
同层重复：路径2（第一个）→2（第二个）和2（第二个）→2（第一个）（非法，生成相同子集）

代码如何避免同层重复：

排序后：重复元素相邻，如[1,2,2]排序后为[1,2,2]
同层判断：在同一层循环中（即同一个父节点的子节点），如果当前元素与前一个元素相同，且前一个元素未被处理（i > start），则跳过当前元素
不同层允许：在不同层（即不同父节点的子节点），允许处理重复元素（如第一个2的子节点和第二个2的子节点独立处理）

2. 条件`i > start`的关键作用

示例说明：处理`nums = [1,2,2]`

第一层循环（start=0，处理元素1）：
- i=0：处理1，无重复，正常选择
- i=1：处理第一个2，i > start(0)为true，但nums[1] != nums[0]，不跳过
- i=2：处理第二个2，nums[2] == nums[1]且i > start(0)，跳过（避免同层重复）
第二层循环（start=1，处理第一个2的子节点）：
- i=1：处理第一个2，start=1，i > start为false，允许处理
- i=2：处理第二个2，nums[2] == nums[1]但i == start(1)，不跳过（不同层允许）

四、去重流程深度模拟：以输入`[1,2,2]`为例

递归调用树与去重节点：

backtracking([1,2,2], 0)
├─ temp=[] → 收集[]
│  ├─ i=0（元素1）：temp=[1] → 收集[1]
│  │  ├─ start=1，处理第二个2（i=1）：temp=[1,2] → 收集[1,2]
│  │  │  ├─ start=2，处理第三个2（i=2）：temp=[1,2,2] → 收集[1,2,2]
│  │  └─ i=2（元素2）：nums[2]==nums[1]且i>start(1)? 否（i=2, start=1，i>start为true，但此时是不同层？不，start=1，i=2>start=1，且nums[2]==nums[1]，但在第二层循环中，start=1，i=2属于同层吗？
│  ├─ i=1（第一个2）：nums[1]==nums[0]? 否，正常处理，temp=[2] → 收集[2]
│  │  └─ start=2，处理第二个2（i=2）：temp=[2,2] → 收集[2,2]
│  └─ i=2（第二个2）：nums[2]==nums[1]且i>start(0) → 是，跳过（同层重复）
└─ i=1（第一个2，start=0）：被i=0处理，i=1正常处理（非重复层）

关键去重步骤：

第一层循环：
- 处理i=0（元素1）后，i=1（第一个2）正常处理
- i=2（第二个2）时，i > start(0)且nums[2]==nums[1]，跳过，避免生成[2]（同层重复）
第二层循环（处理元素1的子节点）：
- i=1（第一个2）时，start=1，i == start，允许处理，生成[1,2]
- i=2（第二个2）时，start=1，i > start，但nums[2]==nums[1]，是否跳过？此时i=2 > start=1，且值相同，跳过？不，原代码中在第二层循环，start=1，i=1时处理第一个2，i=2时，i > start(1)为true，且nums[2]==nums[1]，所以跳过。哦，这里之前模拟有误，正确逻辑是：在处理元素1的子节点（start=1）时，i从1开始，i=1处理第一个2，i=2处理第二个2时，因为i>start(1)且值相同，所以跳过。但这样会导致无法生成[1,2,2]吗？不，原代码中在start=1，i=1时处理第一个2，递归到start=2，此时处理第二个2是允许的，因为在子层中i=2等于start=2，不会触发跳过条件。

正确模拟：

当处理start=1（元素1的子节点，即处理完1之后，处理后面的2），i=1（第一个2），此时start=1，i=1不大于start，所以允许处理，加入temp，递归到start=2，处理i=2（第二个2），此时i=2等于start=2，允许处理，生成[1,2,2]。

五、去重条件的数学证明

命题：`i > start && nums[i] == nums[i-1]` 可消除同层重复子集

证明步骤：

排序保证相邻重复：排序后重复元素相邻，nums[i] == nums[i-1]仅当两者重复
同层与异层区分：
- 同层：i > start，说明i和i-1在同一层循环（同一个父节点的子节点），如父节点是1，子节点是第一个2和第二个2
- 异层：i == start，说明i是当前层的第一个元素，即使与上层元素相同，属于不同路径（如父节点是2，子节点是另一个2）
重复子集的产生场景：
- 同层选择相邻重复元素会生成相同子集（如选择第一个2和第二个2在同层）
- 异层选择重复元素属于不同路径（如父节点是1选择第一个2，父节点是2选择第二个2）

结论：

该条件确保在同一路径的同一层中，相同元素仅被处理一次，从而消除重复子集，同时保留不同层的合法选择。

六、算法复杂度分析

1. 时间复杂度

O(n × 2^n)：
- 子集总数为2^n（去重后最多2^n个子集）
- 每个子集需O(n)时间复制到结果集
- 排序时间O(n log n)，总体为O(n × 2^n + n log n)

2. 空间复杂度

O(n)：
- 递归栈深度最大为n
- temp列表长度最多为n
- 结果集空间O(n × 2^n)

七、常见误区与优化建议

1. 忽略排序的重要性

错误做法：未排序直接去重

// 缺少Arrays.sort(nums)
if (i > 0 && nums[i] == nums[i - 1]) continue; // 错误，无法保证同层重复

后果：重复元素不相邻，条件判断失效，无法正确去重

2. 条件判断错误

误区：使用i > 0代替i > start

if (i > 0 && nums[i] == nums[i - 1]) continue; // 错误，会误杀异层重复

正确逻辑：必须判断i > start，确保是同层重复而非异层

3. 优化建议：位运算去重

// 位运算解法（仅作示意，不推荐）
Set<List<Integer>> set = new HashSet<>();
for (int mask = 0; mask < (1 << n); mask++) {List<Integer> subset = new ArrayList<>();for (int i = 0; i < n; i++) {if ((mask & (1 << i)) != 0) {subset.add(nums[i]);}}set.add(subset);
}
res.addAll(set);