子集

LeetCode 官方题目链接

1. 题目呈现

LeetCode 78. Subsets

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

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

示例 1：

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

示例 2：

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

2. 思路拆解

子集 问题也是一道经典的回溯题目。

核心思想： 我们需要找出数组中所有元素的组合。与全排列不同的是，子集问题中元素的顺序不重要（即 {1, 2} 和 {2, 1} 是同一个子集），且子集的长度是变化的。

回溯法框架：

1. 路径 (path)：记录当前已经选择的子集元素。
2. 选择列表：为了避免重复生成子集（例如 [1, 2] 和 [2, 1]），我们需要规定一个顺序。我们通过维护一个 start 索引，规定每次递归只能从 start 索引之后的元素中选择。
3. 收集结果：与全排列不同，子集问题不需要等到路径长度达到 n 才收集。树上的每一个节点（即每一次递归调用时的 path）都是一个合法的子集。

详细步骤：

• 定义一个递归函数 backtrack(start, path)。
• 每次进入函数，直接将当前 path 加入结果集 res。
• 遍历 i 从 start 到 nums.length - 1：
  • 做选择：将 nums[i] 加入 path。
  • 递归调用 backtrack(i + 1, path)（注意是 i + 1，表示下一个元素只能选 i 后面的）。
  • 撤销选择（回溯）：将 nums[i] 从 path 移除。

3. 代码实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const res = [];
    
    // backtrack 函数
    // start: 当前遍历到的 nums 的索引起点
    // path: 当前已生成的子集
    const backtrack = (start, path) => {
        // 收集子集
        // 注意：这里不需要终止条件，因为我们要收集树上的所有节点
        // 每次进入函数，path 都是一个新的合法子集
        res.push([...path]);
        
        // 遍历选择列表
        for (let i = start; i < nums.length; i++) {
            // 做选择
            path.push(nums[i]);
            
            // 递归进入下一层
            // 传入 i + 1，确保不重复使用元素，且保证子集元素的相对顺序与原数组一致
            backtrack(i + 1, path);
            
            // 撤销选择 (回溯)
            path.pop();
        }
    };
    
    backtrack(0, []);
    return res;
};

4. 运行结果

console.log(subsets([1, 2, 3]));
// 输出:
// [
//   [], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ],
//   [ 1, 3 ], [ 2 ], [ 2, 3 ], [ 3 ]
// ]

5. 复杂度分析

• 时间复杂度：$O(n \times 2^n)$。
  • 一个长度为 $n$ 的数组，其子集总共有 $2^n$ 个。
  • 对于每个子集，我们需要 $O(n)$ 的时间来构造（复制数组）。
  • 所以总时间复杂度是 $O(n \times 2^n)$。
• 空间复杂度：$O(n)$。
  • 递归调用栈的深度最大为 $n$。
  • path 数组的大小最大为 $n$。
  • 不考虑结果集 res 占用的空间。