子集

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

解法一（回溯）：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> path;
        backtrack(nums, 0, path, ans);
        return ans;
    }

private:
    void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& ans) {
        ans.push_back(path);

        for (int i = start; i < nums.size(); ++i)
        {
            path.push_back(nums[i]);
            backtrack(nums, i + 1, path, ans);
            path.pop_back();
        }
    }
};

解法二（二进制枚举）：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;

        for (int mask = 0; mask < (1 << n); ++mask)
        {
            vector<int> subset;
            for (int i = 0; i < n; ++i)
            {
                if (mask & (1 << i))
                {
                    subset.push_back(nums[i]);
                }
            }
            ans.push_back(subset);
        }

        return ans;
    }
};

核心思想

求所有子集，本质上是给数组中的每个元素做一个「选或不选」的决定。

有 n 个元素，每个元素都有 2 种选择，所以一共会产生：

2^n

个子集。

这题最关键的观察是：

一个子集可以用一个长度为 n 的二进制串来表示，第 i 位为 1 表示选中 nums[i]，为 0 表示不选。

例如 nums = [1,2,3] 时：

000 -> []
001 -> [1]
010 -> [2]
011 -> [1,2]
100 -> [3]
101 -> [1,3]
110 -> [2,3]
111 -> [1,2,3]

所以既可以用回溯去枚举所有「选或不选」的组合，也可以直接遍历 0 到 2^n - 1 的每个二进制数。

解法一：回溯

回溯法枚举所有子集，核心是「按起点递增」的写法。

记录当前子集

ans.push_back(path);

这一步放在递归函数的最开头，表示「当前的 path 本身就是一个合法子集」。

因为空集也是合法子集，所以第一次调用时，path 为空，会先把空集加入答案。

枚举起点

for (int i = start; i < nums.size(); ++i)
{
    path.push_back(nums[i]);
    backtrack(nums, i + 1, path, ans);
    path.pop_back();
}

参数 start 表示「下一个可以选的元素从哪个下标开始」。

每次递归都从 start 开始往后选，并且递归下一层时把起点设为 i + 1，这样：

• 元素的下标在子集中严格递增
• 不会出现 [1,2] 和 [2,1] 这样的重复

选完一个元素后递归处理后面的元素，回来时再把它弹出，恢复现场。

解法二：二进制枚举

二进制枚举是这题最简洁的写法。

枚举所有 mask

for (int mask = 0; mask < (1 << n); ++mask)

mask 从 0 到 2^n - 1，每个 mask 的二进制形式对应一种「选或不选」的方案。

按位取出被选中的元素

for (int i = 0; i < n; ++i)
{
    if (mask & (1 << i))
    {
        subset.push_back(nums[i]);
    }
}

如果 mask 的第 i 位是 1，就把 nums[i] 加入当前子集。

加入答案

ans.push_back(subset);

每个 mask 构造出一个子集，加入答案。

边界情况

如果 nums 只有一个元素，例如 [0]：

• 回溯法：先加入空集 []，再枚举到 0，得到 [[],[0]]
• 二进制枚举：mask 为 0 得到 []，为 1 得到 [0]

如果 nums 长度达到上限 10：

• 子集总数是 2^10 = 1024 个，完全在可接受范围内

题目保证元素互不相同，所以不需要额外的去重逻辑。

如果元素可能重复，则需要先排序再去重，但本题不涉及。

正确性证明

我们证明：算法枚举出且仅枚举出 nums 的所有子集。

结论 1：每个答案都是一个合法的子集

回溯法中，path 始终是 nums 的若干个互不相同元素组成的集合，因此是一个合法子集。

二进制枚举中，每个 subset 都是从 nums 中按 mask 选出的若干元素，因此也是合法子集。

结论 2：不会漏掉任何子集

回溯法中，对每个起点 i，都有「选 nums[i]」和「不选 nums[i]」两条分支，递归树覆盖了所有组合。

二进制枚举中，mask 遍历了 0 到 2^n - 1 的全部整数，每一个子集都对应唯一的一个 mask，因此一个都不会漏。

结论 3：不会产生重复的子集

回溯法中，由于起点严格递增，同一个子集只会以唯一的元素顺序被构造一次。

二进制枚举中，mask 与子集是一一对应的，不会重复。

因此枚举结果不重不漏。

得出结论

由结论 1、2、3 可知，算法返回的结果恰好是 nums 的所有子集。

因此两个解法都正确。

举例理解

以：

nums = [1,2,3]

为例，看二进制枚举的过程。

这里 n = 3，mask 从 0 到 7：

最终得到：

[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

和示例输出一致。

复杂度分析

解法一

一共有 2^n 个子集，每个子集在加入答案时都需要 O(n) 的时间复制。

• 时间复杂度：O(n * 2^n)
• 空间复杂度：O(n)，递归栈深度和 path 的最大长度都是 n，不计输出数组

解法二

外层枚举 2^n 个 mask，内层对每个 mask 遍历 n 个元素。

• 时间复杂度：O(n * 2^n)
• 空间复杂度：O(n)，只保存当前子集，不计输出数组

其中 n = nums.length。

两种解法复杂度相同，二进制枚举更简洁，是推荐写法。