78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

回溯

子集问题即无重不可复选长度不限。因为不限制长度，所以每次子递归都要把track加入res

无重不可复选组合，因为是求所有的子集，所以不需要设置结束条件，等for循环结束就自动结束了。

横向代表for循环，纵向代表子递归

class Solution {
    //定义二维数组res用于存储结果
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> subsets(int[] nums) {
        //定义路径数组
        List<Integer> track = new LinkedList<>();
        // 注意track既可以是全局变量也可以是递归参数。
        backtrack(nums, 0, track);
        return res;
    }

    public void backtrack(int[] nums, int start, List<Integer> track) {
        // 每次进入回溯函数，都将当前路径（子集）加入结果集。重点。
        res.add(new LinkedList<>(track));
        
        //for循环遍历数组nums，结束条件被包含在for循环中，因为如果索引越界，则不会进入for循环。
        for (int i = start; i < nums.length; i++) {
            //做选择，将选择添加到路径数组中。回溯是先做选择（提前把子信息加入track）再进入子递归。
            track.add(nums[i]);
            //回溯，继续向后遍历。子集组合问题的选择空间是后面的数
            backtrack(nums, i + 1, track);
            //撤销选择，将选择从路径中删除。这行代码不能删！
            // 不要以为track是参数就可以删掉回溯，做选择和撤销选择是成对出现的，要删必须同时删。
            // 但是删掉后我们无法在参数里为track添加元素。
            track.remove(track.size() - 1);
        }
    }
}

• 时间复杂度：一共 ${n \choose 0} + {n \choose 1} + \cdots + {n \choose n} = (1+1)^n = 2^n$ 个状态，每个状态需要 $O(1)$ 的时间构造子集。

• 空间复杂度：track最大需要O(n)，递归栈需要O(n)，res需要 ${n\choose 0}*0+{n\choose 1}*1+\cdots+{n\choose n}*n=n*2^{n-1}$。

BFS

类似17. 电话号码的字母组合的队列解法，有个区别就是本解法只添加新子集，不删除已有子集，17的队列解法需要删除已有字符串。

dp[i]表示前i个数的解集，dp[i] = dp[i - 1] + collections(i)。其中，collections(i)表示把dp[i-1]的所有子集都加上第i个数形成的子集。 类似BFS。遍历数组，遍历已有子集，把当前数加入已有子集的拷贝得到新子集，加入解集。

可以这么表示，dp[i]表示前i个数的解集，dp[i] = dp[i - 1] + collections(i)。其中，collections(i)表示把dp[i-1]的所有子集都加上第i个数形成的子集。

【具体操作】

因为nums大小不为0，故解集中一定有空集。令解集一开始只有空集，然后遍历nums，每遍历一个数字，拷贝解集中的所有子集，将该数字与这些拷贝组成新的子集再放入解集中即可。时间复杂度为O(n^2)。

1. 例如[1,2,3]，一开始解集为[[]]，表示只有一个空集。
2. 遍历到1时，依次拷贝解集中所有子集，只有[]，把1加入拷贝的子集中得到[1]，然后加回解集中。此时解集为[[], [1]]。
3. 遍历到2时，依次拷贝解集中所有子集，有[], [1]，把2加入拷贝的子集得到[2], [1, 2]，然后加回解集中。此时解集为[[], [1], [2], [1, 2]]。
4. 遍历到3时，依次拷贝解集中所有子集，有[], [1], [2], [1, 2]，把3加入拷贝的子集得到[3], [1, 3], [2, 3], [1, 2, 3]，然后加回解集中。此时解集为[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>(); // 解集
        lists.add(new ArrayList<Integer>()); // 首先将空集加入解集中
        
        // 遍历每个元素。也可以先遍历已有子集，再遍历元素。
        for(int i = 0; i < nums.length; i++){
            int size = lists.size(); // 解集中的子集数
            
            for(int j = 0; j < size; j++){ // 遍历已有子集
                List<Integer> newList = new ArrayList<>(lists.get(j));// 拷贝子集，但不弹出。
                newList.add(nums[i]); // 向拷贝的子集中加入当前数形成新的子集
                lists.add(newList); // 向lists中加入新子集
            }
        }
        return lists;
    }
}

时间复杂度分析

1. 外层循环：

   • 外层 for 循环遍历数组的每个元素，执行次数为 n，其中 n 是数组的长度。

2. 内层循环：

   • 对于每个元素，内层 for 循环遍历当前结果集中已有的子集。
   • 在第 i 次外层循环时，子集的数量为 (2^i)，因为每次迭代时，每个现有子集都可以通过加入当前元素形成一个新的子集。

3. 新子集的生成：

   • 对于每个现有子集，复制并添加当前元素形成一个新的子集，这个操作的时间复杂度为 (O(m))，其中 (m) 是当前子集的长度。
   • 平均来说，每个子集的长度可以认为是 (O(i))（因为从空集开始增长，直到所有元素都被包含）。

4. 综合复杂度：

   • 整个算法的时间复杂度由每个元素生成新子集的过程决定。

   • 每次迭代时需要处理的子集数呈指数增长，因此总的时间复杂度为：

     $$O\left(\sum_{i=0}^{n-1} 2^i \times i\right) = O(n \times 2^n)$$

空间复杂度分析

1. 结果存储空间：

   • 存储所有子集需要的空间与子集的数量和大小相关。
   • 子集的数量是 (2^n)，每个子集的平均长度为 (O(n))，因此存储子集的空间复杂度为 (O(n \times 2^n))。

2. 辅助空间：

   • 辅助空间主要用于存储临时子集 newList，该空间的复杂度是与单个子集长度相关，即 (O(n))，由于是动态创建的，并随即加入列表中，因此不影响整体空间复杂度。

3. 总结空间复杂度：

   • 总体空间复杂度为 (O(n \times 2^n))，这是因为所有子集都被存储在 lists 中。