子集 图解题解

子集问题的解空间有多大

每个元素只有两种命运：进当前子集，或不进。n 个元素的取舍彼此独立，组合起来一共 2ⁿ 个子集，空集和全集都算数。示例 [1,2,3] 正好 8 个。既然要求输出全部子集，任何算法都至少要把这 2ⁿ 个结果各生成一遍，指数级不可避免——问题只剩下：怎么枚举得不重、不漏、代码还短。

为什么用回溯而不是写循环

两层、三层嵌套循环只能枚举固定长度的组合，而子集长度从 0 到 n 都有，循环层数根本写不死。回溯（backtracking）用递归把「逐个元素决定选不选」展开成一棵搜索树：path 记录当前已选的元素，向下走一步等于多选一个数，这条分支探完就把刚选的数弹出来复原，换下一个分支。「选择→递归→撤销」三拍循环，让同一条 path 反复复用于所有分支，省去每次重建的开销。

start 参数为什么能保证不重不漏

子集是组合不是排列，[1,2] 和 [2,1] 算同一个。防重的手法是给递归传 start：每层只从 start 往后挑，选中下标 i 之后，下一层从 i + 1 起步，绝不回头。这样任何子集内部的下标都严格递增，而「一个子集」和「它按下标升序的选取路径」一一对应——每个子集恰好被生成一次，也不会有谁被跳过。这是所有组合类回溯题共用的去重套路。

为什么每个节点都收集而不只在叶子收

很多回溯题只在「凑满条件」的叶子处收集答案，本题不同：搜索树上每一个节点手里的 path 本身就是一个合法子集——空 path 对应空集，走了一步的 path 对应单元素子集。所以递归一进门就先收集，正好把 2ⁿ 个子集一一收齐，一个不多一个不少。

收集时必须存副本，写 res.append(path[:]) 而不是 res.append(path)：path 自始至终是同一个列表引用，后续的撤销操作会把已经存进结果里的内容一并改掉，这是本题最隐蔽的坑。

复杂度怎么数，还有别的枚举法吗

子集共 2ⁿ 个，每个收集时要花 O(n) 复制，总时间 O(n·2ⁿ)；递归深度和 path 长度都不超过 n，辅助空间 O(n)，不计结果本身。两个常见延伸：若数组含重复元素（LC90 子集 II），先排序，同一层遇到与前一个相同的值就跳过；不想写递归可以用位掩码枚举——把 0 到 2ⁿ - 1 的每个整数看作一种选取方案，二进制某位为 1 就选对应元素，复杂度相同，但少了递归的直观结构。

Python

def subsets(nums):
    res = []
    def backtrack(start, path):
        res.append(path[:])          # 每个节点都收集一个子集
        for i in range(start, len(nums)):
            path.append(nums[i])     # 选 i
            backtrack(i + 1, path)   # 只从 i+1 往后，避免重复
            path.pop()               # 撤销，回溯
    backtrack(0, [])
    return res

C++

vector<vector<int>> subsets(vector<int>& nums){
    vector<vector<int>> res; vector<int> path;
    function<void(int)> bt = [&](int start){
        res.push_back(path);                 // 收集
        for(int i = start; i < nums.size(); ++i){
            path.push_back(nums[i]);         // 选
            bt(i + 1);                       // 往后递归
            path.pop_back();                 // 撤销
        }
    };
    bt(0); return res;
}

Java

public List<List<Integer>> subsets(int[] nums){
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}
private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res){
    res.add(new ArrayList<>(path));          // 收集当前 path 的副本
    for(int i = start; i < nums.length; i++){
        path.add(nums[i]);                   // 选 i
        backtrack(nums, i + 1, path, res);   // 只往后，start=i+1
        path.remove(path.size() - 1);        // 撤销，回溯
    }
}