给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
1
2
3
4
5
6
7
8
9
10
11
12
| 输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
|
方法一：回溯搜索
执行一次深度优先搜索，一条路走到底，走不通的是否，返回回来，继续执行，一直递归，直到回到起点。
我们可以画出搜索路径。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
dfs(nums, 0, new ArrayDeque<Integer>());
return ans;
}
public void dfs(int[] nums, int start, Deque<Integer> path){
ans.add(new ArrayList<Integer>(path));
for(int i = start; i < nums.length; i++){
path.addLast(nums[i]);
dfs(nums, i + 1, path);
path.removeLast();
}
}
}
|
方法二：位运算
对于数组 nums 中的每个数来说，有选和不选两种选择，我们可以使用二进制位来代替。”1“代表选中，”0“代表不选中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
int len = nums.length;
int n = 1 << len;
for(int i = 0; i < n; i++){
List<Integer> cur = new ArrayList<>();
for(int j = 0; j < len; j++){
if( ((i >> j) & 1) == 1 ){
cur.add(nums[j]);
}
}
ans.add(cur);
}
return ans;
}
}
|