【LeetCode刷题日记】78.子集
🔥个人主页：代码不加冰（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：LeetCode刷题日记 ， 苍穹外卖日记，SSM框架深入，JavaWeb，
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！
前言：
大家好，我是代码不加冰，今天是依旧是一整天的课，甚至晚自习还跑不掉了，被迫复习了一天高数和概率论，然后空闲时间玩了玩claude，自己做了点小东西，还是挺有意思的，闲话就不多说了，让我们进入每日 的刷题环节。
摘要：
整体来说还是很简单的，跟前面一个模板。本文介绍了使用回溯算法求解数组所有子集的问题。通过分析子集与组合的区别，作者指出子集问题需要记录搜索树的所有节点而非仅叶子节点。文章详细讲解了回溯三部曲（参数、终止条件、单层逻辑），并给出Java代码实现，通过示例[1,2,3]逐步演示了递归过程。该算法通过从startIndex开始遍历避免重复子集，时间复杂度为O(N×2^N)。最后提供了完整解题代码
题目背景：
给你一个整数数组
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] <= 10nums中的所有元素互不相同
题目分析：
求子集问题和77.组合和131.分割回文串又不一样了。
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。
那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始
什么时候for可以从0开始呢
求排列问题的时候，就要从0开始，因为集合是有序的，{1, 2} 和{2, 1}是两个集合，排列问题我们后续的文章就会讲到的。
以示例中nums = [1,2,3]为例把求子集抽象为树型结构，如下：
从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合
回溯三部曲
递归函数参数
全局变量数组path为子集收集元素，二维数组result存放子集组合。（也可以放到递归函数参数里）
递归函数参数在上面讲到了，需要startIndex。
递归终止条件
从图中可以看出：
剩余集合为空的时候，就是叶子节点。
那么什么时候剩余集合为空呢
就是startIndex已经大于数组的长度了，就终止了，因为没有元素可取了，代码如下:
if (startIndex >= nums.size()) { return; }其实可以不需要加终止条件，因为startIndex >= nums.size()，本层for循环本来也结束了。
- 单层搜索逻辑
求取子集问题，不需要任何剪枝，因为子集就是要遍历整棵树。
代码逐行解析
java public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); backtrack(result, new ArrayList<>(), nums, 0); return result; }result：存放所有子集。调用
backtrack从索引 0 开始构建子集。
java private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) { // 每次进入递归，先把当前路径（子集）加入结果 result.add(new ArrayList<>(tempList)); for (int i = start; i < nums.length; i++) { tempList.add(nums[i]); // 选择当前元素 backtrack(result, tempList, nums, i + 1); // 继续往后选 tempList.remove(tempList.size() - 1); // 撤销选择（回溯） } }4. 执行过程图解（以 nums = [1,2,3] 为例）
text 初始：tempList = [] → 加入 [] 到结果 i=0: 选1 → tempList=[1] → 加入 [1] i=1: 选2 → [1,2] → 加入 [1,2] i=2: 选3 → [1,2,3] → 加入 [1,2,3] i=3 退出 撤销3 → [1,2] i=2: 选3 → [1,3] → 加入 [1,3] 撤销3 → [1] 撤销2 → [1] 撤销1 → [] i=1: 选2 → [2] → 加入 [2] i=2: 选3 → [2,3] → 加入 [2,3] 撤销3 → [2] 撤销2 → [] i=2: 选3 → [3] → 加入 [3] 撤销3 → [] 最终结果顺序： [] [1] [1,2] [1,2,3] [1,3] [2] [2,3] [3]5. 为什么不会重复
每次递归只从
start开始，不会回头选之前已经考虑过的元素。保证了每个子集生成时，元素顺序与数组原始顺序一致，避免了
[1,2]和[2,1]这种重复。
6. 复杂度分析
时间复杂度：O(N × 2^N)
一共有 2^N 个子集，每个子集复制到结果时平均长度 O(N)。空间复杂度：O(N)（递归栈深度） + O(2^N × N)（存储所有结果）。
题目答案：
class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); backtrack(result, new ArrayList<>(), nums, 0); return result; } private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) { // 将当前子集加入结果集 result.add(new ArrayList<>(tempList)); // 从 start 开始，尝试将每个元素加入子集 for (int i = start; i < nums.length; i++) { tempList.add(nums[i]); // 选择当前元素 backtrack(result, tempList, nums, i + 1); // 递归处理下一个元素 tempList.remove(tempList.size() - 1); // 撤销选择 } } }结语：
如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！