78. 子集

题目链接：https://leetcode.cn/problems/subsets/

代码

function subsets(nums: number[]): number[][] {
    const res = [];
    const len = nums.length;
    const path = [];
    function dfs(i) {
        res.push([...path]);

        for (let j = i; j < len; j++) {
            path.push(nums[j])
            dfs(j + 1);
            path.pop()
        }
    }
    dfs(0);
    return res;
};

思路

使用回溯枚举所有可能的子集：

1. 定义结果数组 res 保存所有子集
2. 使用 path 记录当前已经选择的元素
3. 递归函数 dfs(i) 表示从下标 i 开始选择元素
4. 每进入一层递归，都先把当前 path 加入结果，因为它本身就是一个合法子集
5. 然后从 i 开始向后枚举，每次选择一个元素加入 path
6. 递归处理后续位置，最后再撤销当前选择

示例

对于 nums = [1,2,3]：

• 一开始 path = []，先加入结果，表示空集
• 选择 1 后，得到 [1]
• 在 [1] 的基础上继续选择 2，得到 [1,2]
• 再选择 3，得到 [1,2,3]
• 回溯后继续尝试 [1,3]、[2]、[2,3]、[3]

关键点

• 每个状态下的 path 都是一个合法子集，所以递归一开始就要收集答案

• 通过 dfs(j + 1) 保证后续只会选择当前位置之后的元素，避免重复

• 回溯的核心仍然是“选择、递归、撤销选择”

• 时间复杂度 $O(n\times 2^n)$，共有 $2^n$ 个子集，每次加入结果需要拷贝当前路径

• 空间复杂度 $O(n)$，主要是递归栈和路径数组开销，不计结果数组