子集 - Stellar Observer Protocol

684 字

3 分钟

子集

2025-08-10

Algorithms

位运算

/

数组

/

回溯

题目描述#

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

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

解题思路#

回溯算法框架：采用 DFS 回溯法遍历所有可能组合，从空集开始逐步添加元素
路径记录：维护当前路径 path，每次递归时记录当前生成的子集
索引控制：使用 start 参数确保元素按顺序选择，避免重复组合
递归展开：每层递归决策”是否添加当前元素”并进入下一层
无剪枝设计：题目要求所有子集，故无需剪枝

关键洞察#

树形结构特性：子集生成可视为二叉树遍历 - 每个元素有”选/不选”两种状态
路径复用机制：回溯时通过 pop() 操作复用数组空间，避免额外内存分配
自动去重原理：索引递增保证元素选择顺序固定，自然避免重复子集
空集处理：初始空路径 [] 确保包含空集
即时收集：每次递归入口记录当前路径，确保所有中间状态都被收集

复杂度分析#

指标	说明
时间复杂度	O(n × 2ⁿ)：生成 2ⁿ 个子集，每个子集平均长度 n/2，复制需 O(n) 时间
空间复杂度	O(n × 2ⁿ)：存储结果所需空间（递归栈 O(n) 可忽略）

代码实现#

递归回溯法

1
/**
2
 * @param {number[]} nums
3
 * @return {number[][]}
4
 */
5
var subsets = function (nums) {
6
    const result = [];
7
    const n = nums.length;
8

9
    const dfs = (start, item) => {
10
        result.push(item);
11
        for (let i = start; i < n; i++) {
12
            dfs(i + 1, [...item, nums[i]])
13
        }
14
    }
15

16
    dfs(0, []);
17

18
    return result;
19
};

迭代法（空间优化）

1
/**
2
 * @param {number[]} nums
3
 * @return {number[][]}
4
 */
5
const subsets = (nums) => {
6
    let res = [[]];
7
    for (const num of nums) {
8
        const newSets = res.map(set => [...set, num]);
9
        res = [...res, ...newSets];
10
    }
11
    return res;
12
};

位运算法（常数优化）

1
/**
2
 * @param {number[]} nums
3
 * @return {number[][]}
4
 */
5
const subsets = (nums) => {
6
    const n = nums.length;
7
    const total = 1 << n;
8
    const res = Array(total);
9
    for (let mask = 0; mask < total; mask++) {
10
        const subset = [];
11
        for (let i = 0; i < n; i++) {
12
            if (mask & (1 << i)) subset.push(nums[i]);
13
        }
14
        res[mask] = subset;
15
    }
16
    return res;
17
};