78. 子集

46. 全排列

中等

给你一个整数数组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中的所有元素互不相同

📝 核心笔记：子集 (Subsets - 选或不选法)

1. 核心思想 (一句话总结)

“每个数字都有两种命运：要么进来，要么滚蛋。”

我们遍历数组中的每一个数字，对于 nums[i]，我们只有两个分支：

1. 不选它：直接跳过，处理下一个。
2. 选它：把它装进path，处理下一个，回来后再把它拿出来（回溯）。

💡图像记忆 (二叉决策树)：

• 这就像走到岔路口。
• 左拐：不带这个行李。
• 右拐：带上这个行李。
• 一直走到路的尽头 (i == n)，也就是对所有行李都做完了决定，这时候拍张照（加入结果集）。

2. 算法流程 (三步走)

1. Base Case (触底)：

• • 当i == nums.length时，说明对所有数字都做过决定了。
  • 此时path里存的就是一种完整的子集方案，复制并加入ans。

1. 分支一：不选 (Exclude)：

• • 啥都不做，直接dfs(i + 1)。

1. 分支二：选 (Include)：

• • path.add(nums[i])。
  • dfs(i + 1)。
  • 回溯：path.removeLast()(恢复现场，为了回退到上一层时不影响其他分支)。

🔍 代码回忆清单 (带注释版)

// 题目：LC 78. Subsets class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); List<Integer> path = new ArrayList<>(); dfs(0, nums, path, ans); return ans; } // i: 当前讨论到了第几个数 private void dfs(int i, int[] nums, List<Integer> path, List<List<Integer>> ans) { // 1. Base Case: 到了数组末尾 (叶子节点) // 这里的逻辑是：必须对每个数都表态后，才结算 if (i == nums.length) { ans.add(new ArrayList<>(path)); // 📸 拍照留念 (深拷贝) return; } // 2. 决策 A: 不选当前数 // 这种写法通常先写"不选"，因为不需要操作 path，代码更清爽 dfs(i + 1, nums, path, ans); // 3. 决策 B: 选当前数 path.add(nums[i]); // 做选择 dfs(i + 1, nums, path, ans); // 递归 path.removeLast(); // 撤销选择 (回溯) } }

⚡ 快速复习 CheckList (易错点)

• [ ]什么时候add到ans？

• • 本解法 (选/不选)：只有在i == n(叶子节点) 时才添加。因为中间过程的path只是半成品状态（虽然也是子集，但在这个逻辑里我们约定只在终点结算）。
  • 对比：如果是for 循环枚举的写法，是进入 DFS 每一步都add。

• [ ]先“选”还是先“不选”？

• • 都行！通常先写“不选”，因为不用写add/remove，代码看着少一行，逻辑也不乱。

• [ ]复杂度是多少？

• • 时间：。每个数 2 种选择，共有 个子集，复制每个子集平均 。
  • 空间：。递归栈深度为 。

🖼️ 数字演练

输入nums = [1, 2]

1. Startdfs(0): 面对 1。
2. Branch "No 1":

• • dfs(1): 面对 2。
  • Branch "No 2":dfs(2)-> 到底 ->Add[]。
  • Branch "Yes 2":path=[2]->dfs(2)-> 到底 ->Add[2]-> 回溯 (pop 2)。

1. Branch "Yes 1":

• • path=[1]->dfs(1): 面对 2。
  • Branch "No 2":dfs(2)-> 到底 ->Add[1]。
  • Branch "Yes 2":path=[1, 2]->dfs(2)-> 到底 ->Add[1, 2]-> 回溯 (pop 2)。
  • 回溯 (pop 1)。

(最终结果：[],[2],[1],[1, 2])