🔥个人主页：代码不加冰（欢迎来访） 🎬作者简介：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] <= 10
- nums 中的所有元素 互不相同
题目分析：
求子集问题和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); // 撤销选择
}
}
}
结语：
如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！
