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]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

解题思路

子集问题是组合问题的典型案例，对于一个长度为 n 的数组，其子集的数量为 2^n。我们可以通过多种方法来生成所有可能的子集：

方法一：基于位运算的迭代法

这个方法基于一个重要观察：对于长度为 n 的数组，可以用一个 n 位二进制数表示某个子集，其中第 i 位为 1 表示选择第 i 个元素，为 0 表示不选择。

关键洞见：从 0 到 2^n-1 的每个二进制数都唯一对应一个子集。

实现步骤

1. 计算子集的总数：2^n。
2. 遍历从 0 到 2^n-1 的每个数字，将其视为二进制掩码。
3. 对于每个掩码，检查哪些位为 1，选择对应位置的元素加入到当前子集中。
4. 将构建好的子集添加到结果中。

方法二：基于回溯的DFS递归法

回溯法是一种通过探索所有可能情况来找到所有解的方法。我们可以通过递归地考虑选择或不选择当前元素来构建所有子集。

关键洞见：对于每个元素，我们有两种选择 - 选择它或不选择它。

实现步骤

1. 使用深度优先搜索 (DFS) 递归遍历所有可能的选择。
2. 遍历数组中的每个元素，对于当前元素，我们可以：
   • 选择它，然后递归处理剩余元素
   • 不选择它，递归处理剩余元素
3. 当我们考虑完所有元素后，将当前构建的子集添加到结果中。

代码实现

下面是两种方法的详细代码实现：

方法一：基于位运算的迭代法

func subsets(nums []int) (res [][]int) {
    n := len(nums)
    // 遍历从0到2^n-1的所有数字
    for mask := 0; mask < 1<<n; mask++ {
        tmp := []int{}
        // 检查mask的每一位是否为1
        for i := 0; i < n; i++ {
            // 如果第i位为1，则选择nums[i]
            if (1<<i)&mask != 0 {
                tmp = append(tmp, nums[i])
            }
        }
        res = append(res, tmp)
    }
    return res
}

方法二：基于回溯的DFS递归法

func subsets(nums []int) (res [][]int) {
    var dfs func(fromIndex, length int)
    // 临时数组，用于存储当前构建的子集
    tmpArray := make([]int, len(nums))

    dfs = func(fromIndex, length int) {
        // 确保索引不越界
        if fromIndex > len(nums) {
            return
        }

        // 将当前子集添加到结果中
        tmp := make([]int, length)
        copy(tmp, tmpArray)
        res = append(res, tmp)

        // 从fromIndex开始遍历，避免重复
        for i := fromIndex; i < len(nums); i++ {
            tmpArray[length] = nums[i]  // 选择当前元素
            dfs(i+1, length+1)         // 递归处理下一个元素
        }
    }

    dfs(0, 0)
    return res
}

方法执行示例

以输入 nums = [1,2,3] 为例：

方法一分析

• mask = 0 (000)：选择 [] → 空集
• mask = 1 (001)：选择 [1]
• mask = 2 (010)：选择 [2]
• mask = 3 (011)：选择 [1,2]
• mask = 4 (100)：选择 [3]
• mask = 5 (101)：选择 [1,3]
• mask = 6 (110)：选择 [2,3]
• mask = 7 (111)：选择 [1,2,3]

方法二分析

回溯法的执行轨迹如下：

1. 初始状态：[]
2. 选择 1：[1] → 递归下去
   • 选择 2：[1,2] → 递归下去
     • 选择 3：[1,2,3] → 递归结束，添加子集
   • 选择 3：[1,3] → 递归结束，添加子集
3. 选择 2：[2] → 递归下去
   • 选择 3：[2,3] → 递归结束，添加子集
4. 选择 3：[3] → 递归结束，添加子集

方法比较

方面	位运算迭代法	回溯DFS递归法
时间复杂度	O(n * 2^n)	O(n * 2^n)
空间复杂度	O(n)	O(n)
优点	实现简洁，直观	更灵活，适用于其他组合问题
缺点	基于位运算，不易扩展	递归开销可能较大
代码复杂度	较低	中等
推荐度	★★★★☆	★★★★★

复杂度分析

时间复杂度

对于两种方法，时间复杂度都是 O(n * 2^n)：

• 方法一：我们需要生成 2^n 个子集，每个子集需要 O(n) 的时间来检查每位并构建。
• 方法二：总共有 2^n 个子集，每个子集需要 O(n) 的时间来构建。

空间复杂度

两种方法的空间复杂度都为 O(n)，不考虑输出结果的空间：

• 方法一：临时数组 tmp 的空间为 O(n)。
• 方法二：递归栈的深度最多为 O(n)，临时数组 tmpArray 的空间为 O(n)。

关键收获

1. 组合问题的位运算技巧：使用二进制位表示选择状态是解决组合问题的有效技巧。
2. 回溯法的应用：回溯法是解决组合、排列问题的通用方法。
3. 数组复制的注意事项：在构建结果时，需要创建新的数组副本而不是直接添加引用。

相关问题

• LeetCode 90: 子集 II（包含重复元素的子集问题）
• LeetCode 46: 全排列
• LeetCode 77: 组合

通过本题，我们可以掌握两种不同的思路来解决子集生成问题，并将这些思路应用到其他类似的组合和排列问题中。