回溯中等1 种解法
#90子集 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
解题主线
- 排序后，同一递归层只选择相同值的第一个下标，便可消除重复子集。
- 相同值仍可沿同一树枝连续选择，因此去重条件必须包含 i > start。
解法 1：排序 + 同层跳过重复值
每个递归节点先收集路径，在同层循环中跳过与前一个候选相同的值。
-
时间复杂度： O(n log n + n × U)，U 为不重复子集数
-
空间复杂度： O(n)，不计输出和排序副本
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
final class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
int[] numbers = nums.clone();
// 排序让相同值相邻，同时保留调用方输入不变。
Arrays.sort(numbers);
List<List<Integer>> result = new ArrayList<>();
backtrack(numbers, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] numbers, int start,
List<Integer> path, List<List<Integer>> result) {
// 每个递归节点代表一个唯一子集，空路径也必须收集。
result.add(new ArrayList<>(path));
for (int i = start; i < numbers.length; i++) {
// 只跳过同层的重复候选；同一树枝仍可连续选择相同值。
if (i > start && numbers[i] == numbers[i - 1]) {
continue;
}
path.add(numbers[i]);
backtrack(numbers, i + 1, path, result);
// 撤销本次选择，恢复父层路径。
path.remove(path.size() - 1);
}
}
}边界与易错点
- 不能全局跳过重复值，否则会漏掉 [2,2] 这类合法子集。
- 空数组也有空集这一答案；旧实现提前返回空结果是不完整的。
- used 数组版本与 i > start 的层去重本质相同，没有必要同时维护两份机械重复解法。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
backtrack/Q090_subsetII.java