【回溯-5】78.子集

题目描述：

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

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

 

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

解题思路：

方法一：回溯 + start 参数

核心思路：

把问题看成树形结构：

• 每个节点都是一个子集

• 从 start 开始遍历，避免重复

• 每个节点都收集结果（不是只有叶子节点）

具体过程示例：

nums = [1,2,3]

                    []  ← 收集
          /         |         \
        [1]        [2]        [3]  ← 收集
        / \         |
     [1,2] [1,3]   [2,3]  ← 收集
      |
   [1,2,3]  ← 收集

所有子集:
[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]

代码实现：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        backtrack(nums, 0, path, result);
        return result;
    }
    
private:
    void backtrack(vector<int>& nums, int start,
                   vector<int>& path, vector<vector<int>>& result) {
        // 每个节点都收集结果（不是只有叶子节点）
        result.push_back(path);
        
        // 从 start 开始遍历，避免重复子集
        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]);           // 选择
            backtrack(nums, i + 1, path, result);  // 递归，传 i+1
            path.pop_back();                   // 撤销
        }
    }
};

复杂度分析：

设 n 是数组长度。

维度	复杂度	说明
时间复杂度	O(n × 2^n)	2^n 个子集，每个子集平均长度 n/2
空间复杂度	O(n)	递归栈深度 + path 长度

关键细节：

1. 为什么每个节点都收集结果？

因为每个节点都是一个子集，不只是叶子节点。比如 [1] 是子集，[1,2] 也是子集。

2. 为什么用 start 参数？

start 控制当前层从哪个位置开始遍历，避免产生重复子集。

例子：nums = [1,2,3]

• 选了 1 后，下一层从 2 开始（i+1），不会选 1 之前的

• 所以不会出现 [2,1] 这种重复子集

3. 为什么递归时传 i+1 而不是 i？

• 传 i+1：不重复选当前元素（子集问题，每个元素只能选一次）

• 传 i：允许重复选（组合总和问题）

4. 和「全排列」的区别

题目	区别
46. 全排列	顺序重要，用 used 标记
78. 子集	顺序不重要，用 start 控制

方法二：位运算（二进制枚举）

思路：用 n 位二进制数表示每个元素选或不选。

代码实现：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> result;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            vector<int> subset;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    subset.push_back(nums[i]);
                }
            }
            result.push_back(subset);
        }
        
        return result;
    }
};

复杂度：时间 O(n × 2^n)，空间 O(n × 2^n)

优点：不需要递归，代码简洁。

缺点：只能处理 n ≤ 20 的情况（2^n 太大）。

方法三：迭代法（逐个添加）

思路：从空集开始，每次把新元素加入已有子集。

代码实现：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result = {{}};
        
        for (int num : nums) {
            int size = result.size();
            for (int i = 0; i < size; i++) {
                vector<int> subset = result[i];
                subset.push_back(num);
                result.push_back(subset);
            }
        }
        
        return result;
    }
};

复杂度：时间 O(n × 2^n)，空间 O(n × 2^n)

三种方法对比：

方法	时间复杂度	空间复杂度	推荐度
回溯 + start	O(n × 2^n)	O(n)	⭐⭐⭐⭐⭐
位运算	O(n × 2^n)	O(n × 2^n)	⭐⭐⭐⭐
迭代法	O(n × 2^n)	O(n × 2^n)	⭐⭐⭐⭐

总结：

要点	说明
核心思想	回溯：每个节点收集结果，从 start 开始遍历
关键操作	result.push_back(path) 放在递归开头
终止条件	没有显式终止条件，遍历完自然结束
时间复杂度	O(n × 2^n)
空间复杂度	O(n)

 

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/m0_73352944/article/details/166942273