XingHuiSama の宝藏之地

给你一个整数数组 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 中的所有元素 互不相同

‍

1. 算法核心思想

本题求解的是数组的幂集（所有可能的子集）。我在这里采用的是回溯算法（DFS 深度优先搜索）。

求解子集问题的核心，可以具象化为一次“闯关选择”游戏。对于数组中的每一个元素，我们都面临一个绝对的二元分支决策：“选”或者“不选”。

如果把每次决策看作树的一个分叉，那么整个探索过程就会自然形成一棵高度为 $N$ 的满二叉树。
我们不需要像“全排列”那样使用复杂的候选集剔除逻辑，只需要维护一个游标 i 不断向后推进。当游标走完整个数组时，我们手里提着的篮子（路径 temp）里装的元素，就是一个合法的子集。

2. 代码逻辑拆解

第一阶段：环境初始化与入口 在主函数 subsets 中，准备好用于存放所有子集的二维大背包 res，以及记录当前探索路径的小篮子 temp。调用辅助函数 func，游标 i 初始指向第 0 个元素。
第二阶段：递归终止条件 (Base Case)

C++
```
if (i == nums.size()) {
    res.push_back(temp);
    return;
}
```
当游标 i 越界（到达数组末尾）时，意味着所有数字都已经做完了“选/不选”的决策。此时 temp 处于一种确定的状态（即一个完整的子集），将其直接记录到结果集 res 中，并 return 结束当前分支。
第三阶段：探索平行宇宙（做决策） 面对当前的数字 nums[i]，代码优雅地分成了两步走：
- 决策 A：不选当前数字 直接调用 func(nums, res, i+1, temp);。这一步什么都没往 temp 里加，带着原样的小篮子，潇洒地走向下一个数字 i+1。
- 决策 B：选当前数字（附带回溯） 先执行 temp.push_back(nums[i]); 将当前数字装入篮子，然后调用 func(nums, res, i+1, temp); 继续往下层探索。探索完毕退回当前层时，必须执行 temp.pop_back();（回溯的灵魂）。因为 temp 是全局共享的引用状态，把刚刚试探性装入的数字弹出来，才能恢复现场，不影响其他分支的运行。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> temp;
        // 从第 0 个数字开始做决策
        func(nums, res, 0, temp);
        return res;
    }

    void func(vector<int>& nums, vector<vector<int>>& res, int i, vector<int>& temp) {
        // 1. 递归终点：所有数字都已做过决策
        if (i == nums.size()) {
            res.push_back(temp);
            return;
        }
        
        // 2. 决策分支一：【不选】当前的数字 nums[i]
        // 直接进入下一层，temp 保持原样
        func(nums, res, i + 1, temp);
        
        // 3. 决策分支二：【选】当前的数字 nums[i]
        temp.push_back(nums[i]);      // 做选择：装进篮子
        func(nums, res, i + 1, temp); // 带着装了新东西的篮子进入下一层
        temp.pop_back();              // 撤销选择：回溯，把刚刚装进去的数字拿出来
    }
};

3. 复杂度分析

时间复杂度：**** $\mathcal{O}(N \times 2^N)$

对于长度为 $N$ 的数组，每个元素都有“选”或“不选” 2 种状态，因此总共有 $2^N$ 个子集（对应二叉树的 $2^N$ 个叶子节点）。在每次到达叶子节点并将 temp 压入 res 时，C++ 底层需要执行一次数组拷贝，最坏情况（全部选中）需要耗时 $\mathcal{O}(N)$ 。因此总体时间复杂度为 $\mathcal{O}(N \times 2^N)$ 。这是生成所有子集不可避免的理论极限，算法已经是最高效的。
空间复杂度：**** $\mathcal{O}(N)$

这里的空间复杂度指辅助空间（不包含最终返回的 res 结果集）。递归调用产生的系统栈最大深度为数组长度 $N$ ；同时我们维护的临时数组 temp 也是在原地上动态增删，其占用的最大内存空间也不会超过 $N$ 。因此，整体辅助空间复杂度为极致的 $\mathcal{O}(N)$ 。

‍