问题描述
给定一个不含重复元素的整数数组 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
的情况。
-
这个方法是解决子集问题的经典方式,希望对你有所帮助!