算法 - 子集（Subsets）

Posted on

1. 题目

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

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

示例:

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

2. 解题思路

子集总数为 2ⁿ，所以任何解法时间复杂度下限就是 O(n·2ⁿ)。常见三种套路：

2.1 回溯法（选 / 不选）

把问题看成遍历一棵决策树：对每个元素做「选它」或「跳过它」的决定。为了避免产生重复子集，引入 start 参数——每层只允许从当前下标往后选，保证结果按下标递增顺序排列。

  • 递归到任意节点时，path 都是一个合法子集（不只是叶子节点），所以进入递归就收集。

  • 时间复杂度：O(n·2ⁿ)，空间复杂度：O(n)（递归栈）。

2.2 迭代法（逐步扩张）

从 [[]] 开始，每遇到一个新数 x，就把已有所有子集各追加一个 x 形成新子集，并入结果。

2.3 二进制枚举

用 0~2ⁿ-1 的每个整数的二进制位表示「第 i 个元素选或不选」，适合炫技。

3. TypeScript 实现

3.1 回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function subsets(nums: number[]): number[][] {
    const res: number[][] = [];
    const path: number[] = [];

    const backtrack = (start: number) => {
        // 每个节点都是一个合法子集
        res.push([...path]);

        for (let i = start; i < nums.length; i++) {
            path.push(nums[i]);       // 选
            backtrack(i + 1);         // 只往后看，避免重复
            path.pop();               // 不选（撤销选择）
        }
    };

    backtrack(0);
    return res;
}

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

3.2 迭代法

1
2
3
4
5
6
7
8
9
10
function subsetsIterative(nums: number[]): number[][] {
    let res: number[][] = [[]];

    for (const x of nums) {
        // 基于「本轮开始前」的子集扩张，不能边遍历边 push 同一数组
        res = [...res, ...res.map((set) => [...set, x])];
    }

    return res;
}

3.3 二进制枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function subsetsBitmask(nums: number[]): number[][] {
    const n = nums.length;
    const res: number[][] = [];

    for (let mask = 0; mask < 1 << n; mask++) {
        const subset: number[] = [];
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) subset.push(nums[i]);
        }
        res.push(subset);
    }

    return res;
}

4. 面试延伸

  • 变体：Subsets II（含重复元素）：先排序，同一层中跳过与前一个相同的值 if (i > start && nums[i] === nums[i-1]) continue;。
  • 回溯三板斧：路径（path）→ 选择列表（start 之后的元素）→ 结束条件（遍历完当前层）。收集时机是本题关键：子集问题在每个节点收集，组合问题通常在叶子收集。
  • 与全排列对比：排列每层从 0 开始并用 used 数组去重，子集/组合用 start 剪枝。

难度：简单 | LeetCode 78 | 回溯入门必考