给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。java源代码 问题分析、算法原理
时间: 2024-05-08 14:20:32 浏览: 5
问题分析:
这是一个经典的回溯算法问题,需要枚举所有可能的子集。对于每个元素,可以选择将其加入当前的子集,也可以选择不加入。最后,将所有的子集加入到结果列表中即可。
算法原理:
1. 初始化一个空列表 res 存放所有子集;
2. 从空列表开始,对于每个元素,分别选择将其加入当前的子集或者不加入;
3. 当子集大小等于原数组大小时,将其加入到结果列表中;
4. 遍历完所有子集,返回结果列表。
Java 代码实现如下:
```
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> cur = new ArrayList<>();
dfs(res, cur, nums, 0);
return res;
}
private void dfs(List<List<Integer>> res, List<Integer> cur, int[] nums, int start) {
if (cur.size() == nums.length) {
res.add(new ArrayList<>(cur));
return;
}
dfs(res, cur, nums, start + 1);
cur.add(nums[start]);
dfs(res, cur, nums, start + 1);
cur.remove(cur.size() - 1);
}
}
```