回溯中等1 种解法

#90子集 II

返回可能含重复值数组的所有不重复子集。

#回溯#数组#排序#去重

解题主线

排序后，同一递归层只选择相同值的第一个下标，便可消除重复子集。

相同值仍可沿同一树枝连续选择，因此去重条件必须包含 i > start。

解法 1：排序 + 同层跳过重复值

每个递归节点先收集路径，在同层循环中跳过与前一个候选相同的值。

时间复杂度

O(n log n + n × U)，U 为不重复子集数

空间复杂度

O(n)，不计输出和排序副本

90. 子集 II · 排序 + 同层跳过重复值

java

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