78.子集

发表于 分类于 阅读次数：

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

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

示例 1：

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

示例 2：

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

解题思路

这是一道经典的回溯题目，考察对子集生成的理解和实现。

核心思想

  • 使用回溯算法生成所有可能的子集
  • 每个元素都有选择和不选择两种状态
  • 当遍历完所有元素时，将当前路径添加到结果中

方法一：回溯法（推荐）

时间复杂度 O(2^n)、空间复杂度 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const result = [];
    
    function backtrack(start, path) {
        // 将当前路径添加到结果中
        result.push([...path]);
        
        // 从start开始，选择后面的元素
        for (let i = start; i < nums.length; i++) {
            // 选择当前元素
            path.push(nums[i]);
            
            // 递归
            backtrack(i + 1, path);
            
            // 撤销选择
            path.pop();
        }
    }
    
    backtrack(0, []);
    return result;
};

方法二：位运算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var subsets = function(nums) {
    const result = [];
    const n = nums.length;
    
    // 遍历所有可能的二进制组合
    for (let i = 0; i < (1 << n); i++) {
        const subset = [];
        
        // 检查每一位
        for (let j = 0; j < n; j++) {
            if (i & (1 << j)) {
                subset.push(nums[j]);
            }
        }
        
        result.push(subset);
    }
    
    return result;
};

方法三：递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var subsets = function(nums) {
    if (nums.length === 0) {
        return [[]];
    }
    
    const first = nums[0];
    const rest = nums.slice(1);
    const subsetsWithoutFirst = subsets(rest);
    
    const result = [...subsetsWithoutFirst];
    
    for (const subset of subsetsWithoutFirst) {
        result.push([first, ...subset]);
    }
    
    return result;
};

方法四：迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var subsets = function(nums) {
    const result = [[]];
    
    for (const num of nums) {
        const newSubsets = [];
        
        for (const subset of result) {
            newSubsets.push([...subset, num]);
        }
        
        result.push(...newSubsets);
    }
    
    return result;
};

解题要点

  1. 回溯法：

    • 使用递归生成所有可能的子集
    • 每个元素都有选择和不选择两种状态
    • 每次递归都将当前路径添加到结果中

  2. 位运算法：

    • 利用二进制数的特性
    • 每个二进制位代表一个元素的选择状态
    • 时间复杂度：O(2^n)

  3. 时间复杂度：

    • 子集数量：2^n
    • 时间复杂度：O(2^n)
    • 空间复杂度：O(n)

面试要点

  • 高频考点：这道题是面试中的高频回溯题
  • 回溯算法：考察对递归和回溯的理解
  • 子集生成：考察对幂集的理解
  • 位运算：了解位运算的应用

相关题目

扩展思考

  1. 为什么使用回溯法？

    • 需要生成所有可能的子集
    • 每个元素都有选择和不选择两种状态
    • 递归结构清晰，易于理解

  2. 时间复杂度分析

    • 子集数量：2^n
    • 时间复杂度：O(2^n)
    • 空间复杂度：O(n)

  3. 不同方法的比较

    • 回溯法：直观，易于理解
    • 位运算法：高效，但不易理解
    • 递归法：逻辑清晰
    • 迭代法：空间效率高

  4. 边界情况

    • 空数组：返回[[]]
    • 单个元素：返回[[], [element]]
    • 两个元素：返回[[], [a], [b], [a,b]]

  5. 实际应用

    • 特征选择
    • 组合优化
    • 数据挖掘

  6. 变种问题

    • 包含重复数字的子集
    • 固定长度的子集
    • 带限制条件的子集

最后更新: 2021-10-03