问题描述
给定一个不含重复元素的整数数组 nums，返回其所有可能的子集（幂集）。
示例
输入： nums = [1,2,3]
输出：
[ [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3] ]
解法：回溯算法
回溯是一种 暴力搜索 方法，它通过 枚举所有可能的解 来解决问题。回溯算法的关键在于：
-
选择：在当前状态下选择一个可行的元素加入子集中。
-
递归：基于当前选择，递归探索剩余元素的子集。
-
回溯：撤销上一步选择，尝试其他可能。
代码实现
import java.util.*;class Solution {public List<List<Integer>> ans = new ArrayList<>();public List<Integer> path = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {dfs(nums, 0);return ans;}public void dfs(int[] nums, int i) {ans.add(new ArrayList<>(path)); // 记录当前子集for (int j = i; j < nums.length; j++) {path.add(nums[j]); // 选择元素 nums[j]dfs(nums, j + 1); // 递归处理剩余元素path.remove(path.size() - 1); // 回溯，撤销选择}}
}
代码解析
1. 变量定义
public List<List<Integer>> ans = new ArrayList<>();
public List<Integer> path = new ArrayList<>();
-
ans：存储所有可能的子集。 -
path：存储当前正在构造的子集。
2. 递归函数
public void dfs(int[] nums, int i) {ans.add(new ArrayList<>(path)); // 记录当前子集for (int j = i; j < nums.length; j++) {path.add(nums[j]); // 选择 nums[j]dfs(nums, j + 1); // 递归path.remove(path.size() - 1); // 回溯}
}
核心逻辑
-
存储当前子集：进入递归时，首先将
path加入ans，确保所有子集都被记录。 -
遍历所有可能的选择：
-
j从i开始，确保所有元素只能被选择一次，避免重复。 -
选择
nums[j]后，递归dfs(nums, j+1)处理剩余元素。
-
-
回溯：递归结束后，撤销上一步的选择（
path.remove()），探索其他可能。
递归执行过程
假设 nums = [1,2,3]，其递归树如下：
dfs(0, []) --> 添加 []├── dfs(1, [1]) --> 添加 [1]│ ├── dfs(2, [1,2]) --> 添加 [1,2]│ │ ├── dfs(3, [1,2,3]) --> 添加 [1,2,3]│ │ └── 回溯到 [1,2]│ ├── dfs(3, [1,3]) --> 添加 [1,3]│ └── 回溯到 [1]├── dfs(2, [2]) --> 添加 [2]│ ├── dfs(3, [2,3]) --> 添加 [2,3]│ └── 回溯到 [2]├── dfs(3, [3]) --> 添加 [3]└── 回溯到 []
最终 ans 存储的子集为：
[ [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3] ]
时间复杂度分析
-
每个元素可以 选或不选，因此总共有
2^n种可能的子集。 -
递归深度为
n，每次递归的操作为O(1)。 -
总时间复杂度：O(2^n * n)，近似
O(2^n)，指数级复杂度。
总结
-
回溯思路：
-
递归枚举所有可能的子集。
-
先将
path存入ans，然后继续选择下一个元素。 -
递归结束后 回溯，撤销上一步的选择。
-
-
避免重复：
-
j从i开始，保证每个元素只被选一次，避免重复子集。
-
-
适用场景：
-
由于时间复杂度为
O(2^n)，适用于n ≤ 20的情况。
-
这个方法是解决子集问题的经典方式，希望对你有所帮助！
