序言
虽然算法很难，但不应该就放弃。这是一个学习笔记，希望你们喜欢~
先自己尝试写，大概十几分钟仍然写不出来
看思路，再尝试跟着思路写
仍然写不出来，再看视频
b站up视频推荐：爱学习的饲养员
leetcode其他文章：
数组篇：
链表篇：
从小白开始刷算法 ListNode 链表篇 leetcode.203
从小白开始刷算法 ListNode 链表篇 leetcode.206
队列篇
从小白开始刷算法 ListNode 链表篇 leetcode.933
栈篇
从小白开始刷算法 Stack 栈篇 leetcode.496
哈希篇
从小白开始刷算法 Hash 哈希篇 leetcode.217
从小白开始刷算法 Hash 哈希篇 leetcode.705
树篇
从小白开始刷算法 Tree 树篇 先序遍历 leetcode.144
从小白开始刷算法 Tree 树篇 中序遍历 leetcode.94
从小白开始刷算法 Tree 树篇 后序遍历 leetcode.94
堆篇
从小白开始刷算法 Heap 堆篇 最大堆排序 leetcode.215
小白开始刷算法 Heap 堆篇 最小堆排序 leetcode.692
双指针篇
二分法篇
滑动窗口篇
递归篇
分治法篇
回溯法篇
回溯法篇
难度：中等
题目：
78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
题目来源：力扣（LeetCode）
回溯法思路
能否写出：不能写出，需要思路。
时间：一个小时多
回溯法（backtrack）介绍：
里面有关于回溯法的介绍
思路：
首先，我们创建一个空的结果列表result，用于存储所有的子集。我们初始化result为一个空列表，表示空集也是nums的子集。
然后，我们遍历长度从1到nums.length的所有子集长度。在每个长度下，我们使用回溯法来生成所有符合要求的子集。
对于长度为length的子集，我们定义一个backtrack方法，其中传入的参数包括:
- nums数组
- 结果列表result
- 子集长度length
- 当前索引index
- 当前正在构建的子集subset
在backtrack函数中，我们首先检查当前subset的长度是否等于length。如果是，说明我们已经构建了一个符合要求的子集，将其添加到结果列表result中。
接下来，我们从索引index开始遍历nums数组，对于每个元素nums[i]，我们将其添加到subset中，并递归调用backtrack函数来构建下一个元素。递归调用时，我们传入的索引index=i+1，表示下一个元素的索引，这样可以确保我们不重复使用已经使用过的元素。
当递归返回后，我们需要将subset中的最后一个元素移除，以便尝试下一个可能的元素。这样可以保证我们得到所有的子集。
最终，当遍历完所有长度的子集时，我们将得到nums的所有子集，存储在结果列表result中，并将其作为函数的返回值。
通过这种回溯法的思路，我们可以找出nums的所有子集。在回溯的过程中，我们逐步构建子集，并根据要求判断是否加入结果列表。通过递归的方式，我们尝试所有可能的选择，最终得到所有符合要求的子集。
subset的作用：
subset是一个用于暂存当前正在构建的子集的列表。它在回溯过程中起到了两个重要的作用：
- 存储当前正在构建的子集元素：
- 在回溯的过程中，每次选择一个元素加入到子集中，然后进行递归，直到满足生成子集的条件。subset列表用于存储当前正在构建的子集元素，通过不断地添加和删除元素，来构建出不同的子集。
- 添加已生成的子集到结果列表：
- 当满足生成子集的条件时（子集长度等于目标长度），需要将当前的子集加入到结果列表中。由于在回溯过程中，使用的是同一个subset列表，为了避免后续操作对已生成的子集造成影响，需要创建一个副本（
new ArrayList<>(subset)）并将其添加到结果列表中。
通过使用subset列表，可以在回溯的过程中动态地构建不同长度的子集，并将满足条件的子集添加到结果列表中，最终得到所有可能的子集组合。
// 仅是我的思路代码，leetcode上大神更厉害 class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); // 初始状态，加入空集 result.add(new ArrayList<>()); // 构建subset的长度 for (int length = 1; length <= nums.length; length++) { backtrack(nums, result, length, 0, new ArrayList<>()); } return result; } private void backtrack(int[] nums, List<List<Integer>> result, int length, int index, ArrayList<Integer> subset) { if (subset.size() == length) { // 构建符合要求的子集，加入结果列表 result.add(new ArrayList<>(subset)); return; } // for (int i = index; i < nums.length; i++) { // 添加当前元素到子集中 subset.add(nums[i]); // 递归构建下一个元素 backtrack(nums, result, length, i + 1, subset); // 回溯，移除最后一个元素，尝试下一个选择 subset.remove(subset.size() - 1); } } }
时间复杂度：
- 在主函数中的
for循环会执行n次，每次调用回溯函数。 - 在回溯函数中，最坏情况下，每个元素都会被选中或不选中，因此回溯函数的时间复杂度为指数级别的 O(2^n)。
- 综合起来，总时间复杂度为 O(n * 2^n)。
空间复杂度：
- 结果列表
result的空间复杂度为 O(2^n)，因为最终结果的个数为 2^n 个。 backtracking函数中使用的临时列表subset的空间复杂度为 O(n)，因为在最坏情况下，递归的深度为 n，即最多会存储 n 个元素。- 综合起来，总空间复杂度为 O(2^n)。
其他思路：
DFS
class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); List<Integer> subset = new ArrayList<>(); dfs(nums, result, subset, 0); return result; } private void dfs(int[] nums, List<List<Integer>> result, List<Integer> subset, int index) { result.add(new ArrayList<>(subset)); for (int i = index; i < nums.length; i++) { subset.add(nums[i]); dfs(nums, result, subset, i + 1); subset.remove(subset.size() - 1); } } }
时间复杂度： O(2^n)
空间复杂度： O(n)
