78. 子集#

上次拆解了全排列问题，今天我们来攻克它的”近亲”——子集问题。这道题看似简单，但想要写出最优解却暗藏玄机。准备好了吗？让我们开启今天的算法之旅！

🛍 从超市购物说起#

小红在超市挑选水果，货架上有苹果、香蕉、橙子。她发现：

• 每种水果都可以选择拿或不拿
• 不同的拿法会形成不同的组合
• 空袋子也是一种有效组合

这不正是子集问题的现实场景吗？

问题描述#

题目目标#

给定一个整数数组 nums ，其中元素互不相同，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集，答案顺序可以任意。

示例 1#

输入： nums = [1,2,3] 输出： [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 说明： 输出顺序不固定

💡 问题的本质#

LeetCode 78题”子集”的描述：

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

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

🤔 关键解题思路是什么？#

与全排列不同，子集问题要求：

1. 元素顺序不影响结果（[1,2]和[2,1]视为同一个子集）
2. 通过索引控制选择范围，避免重复组合
3. 每个节点状态都是有效解（即时记录路径）

🎬 模拟运行：回溯树深度解析#

以nums=[1,2,3]为例，看算法如何生成所有子集：

初始状态：空路径[]

• 第一层决策：选择起始元素
  • 选1 → 路径[1]
    • 第二层决策：在1之后选择
      • 选2 → 路径[1,2]
        • 第三层决策：在2之后选择
          • 选3 → 路径[1,2,3]
      • 选3 → 路径[1,3]
  • 选2 → 路径[2]
    • 第三层决策：在2之后选择
      • 选3 → 路径[2,3]
  • 选3 → 路径[3]

每个决策节点都会将当前路径加入结果集！

⚡ 代码实现：优雅的回溯解法#

class Solution {
    // 主函数：返回 nums 的所有子集（幂集）
    public List<List<Integer>> subsets(int[] nums) {
        // res：保存所有子集结果
        List<List<Integer>> res = new ArrayList<>();
        // 从下标 0 开始回溯，初始路径为空
        backtrack(nums, 0, new ArrayList<>(), res);
        // 返回全部子集
        return res;
    }

    // 回溯函数：从 start 开始选择元素，构造后续子集
    private void backtrack(int[] nums, int start, 
                          List<Integer> path, List<List<Integer>> res) {
        // 每到一个节点，当前 path 都是一个合法子集，先加入结果
        // 这里同样要拷贝，避免后续回溯修改影响结果
        res.add(new ArrayList<>(path));

        // 从 start 开始枚举可选元素，保证不会产生重复组合
        for (int i = start; i < nums.length; i++) {
            // 做选择：把 nums[i] 加入当前子集
            path.add(nums[i]);
            // 递归到下一层：下次只能从 i+1 开始选，避免重复使用前面的元素
            backtrack(nums, i + 1, path, res);
            // 撤销选择（回溯）：移除刚加入的元素，尝试下一个分支
            path.remove(path.size() - 1);
        }
    }
}

🎯 算法核心要点#

1. 索引控制：通过start参数限制选择范围，避免重复组合
2. 即时记录：每次递归都保存当前状态，不漏掉任何子集
3. 剪枝优化：自然避免了逆序组合的出现

📊 复杂度分析#

时间复杂度：O(n×2ⁿ)

• 生成所有2ⁿ个子集
• 每个子集需要O(n)时间复制

空间复杂度：O(n)

• 递归栈深度最大为n
• 临时路径存储空间

🎯 面试官灵魂拷问#

Q：如果数组包含重复元素怎么办？
A：先排序，回溯时跳过相邻重复元素（对应LeetCode 90题）

Q：如何只输出大小为k的子集？
A：在终止条件中增加长度判断（对应LeetCode 77题组合问题）

Q：如何用迭代法实现？
A：通过位掩码表示元素选择状态，例如3位二进制数对应8种子集

💡 举一反三#

同类型问题：

• 组合总和（LeetCode 39）
• 子集II（LeetCode 90）
• 字母大小写全排列（LeetCode 784）
• 分割回文串（LeetCode 131）

🎁 思考题#

给定一个含重复元素的数组nums，如何高效生成所有不重复子集？要求时间复杂度低于O(2ⁿ)是否可能？

欢迎在评论区分享你的思路，我们将在下期题解中揭晓答案！

📝 代码模板总结#

子集问题的通用解法：

1. 将当前路径加入结果集
2. 遍历可选择的元素范围
3. 做出选择并更新索引
4. 递归处理后续元素
5. 撤销选择继续尝试