78. 子集

难度：🟡 Medium | 标签：回溯、位运算 | 状态：⬜ LeetCode 链接

思路

每个元素：选 或 不选。 回溯框架：递归到 i == n 时把当前 path 加入结果。

代码

class Solution {
    vector<vector<int>> res;
    vector<int> path;
    void dfs(vector<int>& nums, int i) {
        if (i == (int)nums.size()) { res.push_back(path); return; }
        // 不选
        dfs(nums, i + 1);
        // 选
        path.push_back(nums[i]);
        dfs(nums, i + 1);
        path.pop_back();
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }
};

复杂度

• 时间 O(n · 2ⁿ)，空间 O(n)

易错 / 回顾

• 也可用 start 模式：每层尝试加 i ∈ [start, n)，每加一个就 push 当前
• 位运算法：i ∈ [0, 2ⁿ)，每位代表选不选
• 含重复（90）：排序 + 同层去重