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

回溯

元素可重不可复选组合。因为元素可能会重复，所以需要排序+剪枝以避免产生重复子集，剪枝即如果当前值等于前一个值，则跳过。因为不可复选，所以子递归的起点要加一，即缩小选择范围。

排序是为了固定重复元素的顺序，固定顺序是为了过滤（或剪枝），过滤是为了不重复。

每次回溯索引都加一，这是为了不复选。

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> track = new LinkedList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 先排序，让相同的元素靠在一起。重点。
        Arrays.sort(nums);
        backtrack(nums, 0);
        return res;
    }

    void backtrack(int[] nums, int start) {
        // 前序位置，每个节点的值都是一个子集。重点。
        res.add(new LinkedList<>(track));

        for (int i = start; i < nums.length; i++) {
            // 横向剪枝，值相同的相邻树枝，只遍历第一条。重点。
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            track.addLast(nums[i]);
            backtrack(nums, i + 1);
            track.removeLast();
        }
    }
}

• 构造新子集：new LinkedList<>(track) 这行代码会创建一个新的 LinkedList 实例，并将当前 track 中的所有元素复制到新列表中。复制 track 的所有元素的时间复杂度是 (O(k))，其中 (k) 是当前 track 的长度。

• 加入结果列表：res.add(...) 是将新子集加入到结果列表 res 中，这个操作本身是常数时间 (O(1))，因为 LinkedList 的尾插入操作时间复杂度为 (O(1))。

在回溯生成子集的过程中，track 的长度会随着递归的深度变化。最坏情况下，track 可以达到最大长度，即 (n)（输入数组的长度）。因此，复制 track 的操作在最坏情况下是 (O(n))。

• 构建子集的复杂度：在递归过程中，每次生成一个新子集都需要将当前 track 的元素复制到一个新的列表中。虽然不是每个子集的长度都达到 (n)，但在最坏情况下，所有可能子集的平均长度可以近似认为是 (O(n))。

• 整体复杂度影响：由于回溯算法需要遍历所有可能的子集组合，每个组合对应一个递归调用，并在每个递归调用中执行上述子集构建操作，这就导致了整体时间复杂度为 (O(n \cdot 2^n))。

综上，时间复杂度为 (O(n \log n + n \cdot 2^n))。排序的时间复杂度在回溯中的指数级复杂度前可忽略，因此总体时间复杂度可以认为是 (O(n \cdot 2^n))。

空间复杂度分析

1. 递归栈空间：

   • 递归调用栈的深度为 (n)，所以递归栈空间复杂度为 (O(n))。

2. 结果存储空间：

   • 存储所有子集的空间需求为 (O(n \cdot 2^n))，因为在最坏情况下，每个子集的长度是 (n)，而子集的数量是 (2^n)。

3. 辅助数据结构：

   • 使用了 track 作为当前子集的存储，其最大长度是 (n)，空间复杂度为 (O(n))。
   • 结果列表 res 存储所有子集，其空间需求已经在上面提到过，主要由子集数量和子集长度决定。

综上，空间复杂度主要由结果存储决定，因此为 (O(n \cdot 2^n))。

• 可能的子集数量为 2^n，对于每一个子集，程序都会执行一系列操作，其中包括子集的构造和检查，平均情况下，每个子集的长度是 O(n)。 回溯搜索的总复杂度可以近似表示为 O(n*2^n)，这是因为回溯会对每个可能的子集进行构建和复制。
• new LinkedList<>(track) 这行代码会创建一个新的 LinkedList 实例，并将当前 track 中的所有元素复制到新列表中。 复制 track 的所有元素的时间复杂度是 O(k)，其中 k 是当前 track 的长度。res.add(...) 是将新子集加入到结果列表 res 中， 这个操作本身是常数时间 O(1)，因为 LinkedList 的尾插入操作时间复杂度为 O(1)。 在回溯生成子集的过程中，track 的长度会随着递归的深度变化。最坏情况下，track 可以达到最大长度，即 n（输入数组的长度）。 因此，复制 track 的操作在最坏情况下是 O(n)。因此如果不考虑结果链表res，空间复杂度是 O(n)。res的空间复杂度是O(n*2^n)。