题目链接 · 灵神原题解（署名来源）

视频讲解

请看【基础算法精讲 14】，制作不易，欢迎点赞~

方法一：选或不选（输入的视角）

对于输入的 $\mathit{\text{nums}}$，考虑每个 $\mathit{\text{nums}}[i]$ 是选还是不选，由此组合出 $2^n$ 个不同的子集。

$\mathit{\text{dfs}}$ 中的 $i$ 表示当前考虑到 $\mathit{\text{nums}}[i]$ 选或不选。

答疑

问：为什么要恢复现场？

答：我们来做个实验。去掉代码中的恢复现场那行代码，然后测试 $\mathit{\text{nums}}=[1,2]$ 这个数据。你会发现答案居然包含 $[2,1,2]$，这是为什么呢？

看视频中的图。如果不恢复现场，当我们从 $[2]$ 递归返回后，$\mathit{\text{path}}$ 中还残留有 $2$，对于后面的递归来说，这个 $2$ 是多余的。继续递归「选 $1$」的右子树时，会把 $1$ 加到 $\mathit{\text{path}}$ 中，导致 $\mathit{\text{path}}=[2,1]$；继续递归到「选 $2$」的右子树时，$\mathit{\text{path}}=[2,1,2]$，显然这是错的。

Python 解法1

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        path = []

        # 选或不选：讨论 nums[i] 是否加入 path
        def dfs(i: int) -> None:
            if i == n:  # 子集构造完毕
                ans.append(path.copy())  # 复制 path，也可以写 path[:]
                return

            # 不选 nums[i]
            dfs(i + 1)  # 考虑下一个数 nums[i+1] 选或不选

            # 选 nums[i]
            path.append(nums[i])
            dfs(i + 1)  # 考虑下一个数 nums[i+1] 选或不选
            path.pop()  # 恢复现场，撤销 path.append(nums[i])

        dfs(0)
        return ans

C++ 解法1

// C++ 版待补充

C++ 解法2

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

        // 选或不选：讨论 nums[i] 是否加入 path
        auto dfs = [&](this auto&& dfs, int i) -> void {
            if (i == n) { // 子集构造完毕
                ans.emplace_back(path);
                return;
            }

            // 不选 nums[i]
            dfs(i + 1); // 考虑下一个数 nums[i+1] 选或不选

            // 选 nums[i]
            path.push_back(nums[i]);
            dfs(i + 1); // 考虑下一个数 nums[i+1] 选或不选
            path.pop_back(); // 恢复现场，撤销 path.push_back(nums[i])
        };

        dfs(0);
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n{2}^n)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。有 $2^n$ 个子集，所以搜索树有 $2^n$ 个叶子，每个叶子复制 $\mathit{\text{path}}$ 需要 $\mathcal{O}(n)$ 的时间，一共需要 $\mathcal{O}(n{2}^n)$ 时间。
• 空间复杂度：$\mathcal{O}(n)$。返回值的空间不计。

方法二：枚举选哪个（答案的视角）

枚举子集（答案）的第一个数选谁，第二个数选谁，第三个数选谁，依此类推。

$\mathit{\text{dfs}}$ 中的 $i$ 表示现在要枚举选 $\mathit{\text{nums}}[i]$ 到 $\mathit{\text{nums}}[n-1]$ 中的一个数，添加到 $\mathit{\text{path}}$ 末尾。

如果选 $\mathit{\text{nums}}[j]$ 添加到 $\mathit{\text{path}}$ 末尾，那么下一个要添加到 $\mathit{\text{path}}$ 末尾的数，就要在 $\mathit{\text{nums}}[j+1]$ 到 $\mathit{\text{nums}}[n-1]$ 中枚举了。

答疑

问：代码的递归边界是什么？为什么没有判断 i == n？

答：当 $i=n$ 时，代码不会进入循环，更不会往下递归。此时 $\mathit{\text{dfs}}(i)$ 只执行了一个逻辑：把 $\mathit{\text{path}}$ 的拷贝添加到 $\mathit{\text{path}}$ 中。

Python 解法3

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        path = []

        # 枚举选哪个：在下标 i 到 n-1 中选一个数，加到 path 末尾
        def dfs(i: int) -> None:
            ans.append(path.copy())  # 不选，把当前子集加入答案
            for j in range(i, n):  # 选，枚举选择的数字
                path.append(nums[j])
                dfs(j + 1)  # 选 nums[j] 意味着 i 到 j-1 都跳过不选，下一个数从 j+1 开始选
                path.pop()  # 恢复现场

        dfs(0)
        return ans

C++ 解法3

// C++ 版待补充

C++ 解法4

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

        // 枚举选哪个：在下标 i 到 n-1 中选一个数，加到 path 末尾
        auto dfs = [&](this auto&& dfs, int i) -> void {
            ans.emplace_back(path); // 不选，把当前子集加入答案
            for (int j = i; j < n; j++) { // 选，枚举选择的数字
                path.push_back(nums[j]);
                dfs(j + 1); // 选 nums[j] 意味着 i 到 j-1 都跳过不选，下一个数从 j+1 开始选
                path.pop_back(); // 恢复现场
            }
        };

        dfs(0);
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n{2}^n)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。答案的长度为子集的个数，即 $2^n$，同时每次递归都把一个数组放入答案，因此会递归 $2^n$ 次，再算上加入答案时复制 $\mathit{\text{path}}$ 需要 $\mathcal{O}(n)$ 的时间，所以时间复杂度为 $\mathcal{O}(n{2}^n)$。
• 空间复杂度：$\mathcal{O}(n)$。返回值的空间不计。

方法三：二进制枚举

根据 从集合论到位运算，常见位运算技巧分类总结 中的「枚举子集」的技巧，可以只用简单的循环枚举所有子集。

Python 解法5

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        for i in range(1 << len(nums)):  # 枚举全集 U 的所有子集 i
            subset = [x for j, x in enumerate(nums) if i >> j & 1]
            ans.append(subset)
        return ans

C++ 解法5

// C++ 版待补充

C++ 解法6

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans(1 << n);
        for (int i = 0; i < (1 << n); i++) { // 枚举全集 U 的所有子集 i
            for (int j = 0; j < n; j++) {
                if (i >> j & 1) { // j 在集合 i 中
                    ans[i].push_back(nums[j]);
                }
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n{2}^n)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。返回值的空间不计。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府