子集 | 每日算法 · 变量语义法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

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

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

示例 1

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

输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

每个元素在子集中「选或不选」，共 2^3=8 种（含空集）。

示例 2

输入：nums = [0]

输出：[[],[0]]

💭 模拟答题者思考

1. 我先想暴力：用 0/1 掩码枚举 2^n 种选法，按位决定是否把 nums[i] 放进子集——思路正确，但实现上若按「排列式」逐位填集合，容易和「顺序不同、集合相同」搞混。

2. 重复在哪里？子集只看「选了哪些数」，{1,2} 与 {2,1} 是同一子集；若每层从 0 重新枚举所有未选元素，会生成大量等价排列。

3. 关键转化：与「组合」同款——维护 start，每层只考虑 nums[start..]，递归传 i+1，使选中元素对应下标单调递增，自然去重。

4. 与组合题的差异：不必等 path 满长才收集；每进入一层 DFS，当前 path 就是一个合法子集（含空集）。例 [1,2,3]：先收 []，再收 [1]、[1,2] 等。

5. n≤10、元素互异，2^n≤1024，回溯足够；也可位运算迭代，但 DFS 更利于扩展到「子集 II」去重。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`path`	list<int>	定义：当前正在构造的子集（按原数组下标递增选取的元素）维护：DFS 在 `path` 末尾追加 `nums[i]`，回溯时 `pop` 撤销更新：进入一层递归前先记录当前 `path`；尝试分支时 `append`，返回后 `pop`
`start`	int	定义：本轮可选元素在 `nums` 中的起始下标（含自身）维护：只从 `start` 往后选，保证子集内下标严格递增，避免同一集合因顺序不同重复出现更新：选了 `nums[i]` 后下一层传 `start = i + 1`
`ans`	list<list<int>>	定义：幂集中全部子集维护：每次进入 DFS 时把当前 `path` 的副本加入（含空集对应的根调用）更新：不在叶子才收集——每一层都代表一个合法子集状态

⌨️ 落码步骤

1. 初始化结果 ans 与当前路径 path

2. 定义 DFS backtrack(start)：先将 path[:] 加入 ans

3. 对 i 从 start 到 len(nums)-1：将 nums[i] 追加到 path

4. 递归 backtrack(i + 1)，探索包含 nums[i] 的后续子集

5. 回溯：从 path 弹出末尾，继续尝试更大的 i

6. 从 backtrack(0) 启动，返回 ans

💻 代码实现

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

        def backtrack(start: int) -> None:
            ans.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return ans

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

        function<void(int)> dfs = [&](int start) {
            ans.push_back(path);
            for (int i = start; i < (int)nums.size(); i++) {
                path.push_back(nums[i]);
                dfs(i + 1);
                path.pop_back();
            }
        };

        dfs(0);
        return ans;
    }
};
// 时间 O(n·2^n)，空间 O(n) 递归栈

📈 复杂度分析

时间复杂度 O(n · 2^n)（共 2^n 个子集，每个拷贝长度至多 n）

空间复杂度 O(n)（递归栈深度与当前路径，不计输出）

⚠️ 常见坑

❗ 只在叶子收集：子集题应在每层 DFS 入口就把当前 path 记入答案，否则漏掉「不再往下选」的中间状态（如只选 [1] 不再选 2、3）。

❗ 未用 start 去重：若 i 每层都从 0 枚举且用「visited」位，也能做对，但更易写错；标准写法是 for (i = start; ...) 且递归 i+1。

❗ 收集答案未拷贝 path：Python 应 ans.append(path[:])；C++ 在 push 时拷贝当前 path 向量，避免回溯污染已存结果。

🔍 必测边界 Case

Case 1：单元素

nums = [0] → [[],[0]]

Case 2：空集必含

任意 nums → ans 中必有一项 []

Case 3：示例 1 规模

nums = [1,2,3] → 共 8 个子集

Case 4：全选

nums = [1,2] → 含 [1,2]

Case 5：互异保证

本题无重复元素，无需排序去重；重复元素见「子集 II」