🚀 力扣热题 78：子集（详细解析）

📌 题目描述

力扣 78. 子集

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

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

🎯 示例 1：

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

🎯 示例 2：

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

✅ 提示：

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

💡 解题思路

1️⃣ 回溯法（Backtracking）

• 子集问题是典型的 回溯问题：我们在每一步都面临两个选择：选或不选当前元素。
• 使用一个递归函数 backtrack(start, path)：
  • 每次递归都将当前路径 path 加入结果集中。
  • 然后从当前起点 start 开始，依次尝试添加每个元素，并继续递归。

2️⃣ 二进制法（迭代法）

• 利用 二进制位映射子集：数组长度为 n，所有子集个数为 2^n，每个子集可由一个 n 位二进制数表示。
• 第 i 位为 1 表示选择 nums[i]，否则不选。

💻 Go 代码实现

✅ 方法一：回溯法

func subsets(nums []int) [][]int {
   
    var res [][]int
    var path []int

    var backtrack func(start int)
    backtrack = func(start int) {
   
        temp := make([]int, len(path))
        copy(temp, path)
        res = append(res, temp)

        for i := start; i < len(nums); i++ {
   
            path = append(path, nums[i])
            backtrack(i + 1)
            path = path[:len(path)-1]
        }
    }

    backtrack(0)
    return res
}

✅ 方法二：二进制迭代法

func subsets(nums []int) [][]int {
   
    n := len(nums)
    total := 1 << n // 2^n 个子集
    res := [][]int{
   }

    for i := 0; i < total; i++ {
   
        subset := []int{
   }
        for j := 0; j < n; j++ {
   
            if (i>>j)&1 == 1 {
   
                subset = append(subset, nums[j])
            }
        }
        res = append(res, subset)
    }
    return res
}

⏳ 复杂度分析

📌 衍生思考

• 回溯问题在算法题中非常常见，类似题型包括：
  • 子集 II（含重复元素）
  • 组合（如 77. 组合）
  • 排列（如 46. 全排列）
• 二进制法思路巧妙，适合用来锻炼位运算思维 💻

🎯 总结

• ✅ 回溯法：经典通用模板，逻辑清晰易扩展。
• ✅ 二进制法：简洁高效，适合面试快速写出解法。
• 💡 掌握多种解法，灵活应对不同场景和面试官提问。

👍 如果觉得有帮助，欢迎点赞 + 收藏 + 关注支持！📌🚀💻✅