求一个数组的所有子集数组

给定一组不含重复元素的整数数组 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

从前往后遍历,新子集就是原子集加上新加的数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
int len = nums.length;
List<Integer> inList = new ArrayList<>();
list.add(inList);
for(int i=0; i<len; i++){
int size = list.size();
for(int j = 0; j<size; j++){
List<Integer> newList = new ArrayList<>(list.get(j));
newList.add(nums[i]);
list.add(newList);
}
}
return list;
}
}

思路2

当成回溯问题求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public List<List<Integer>> subsets(int[] nums) {
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
// 如果有重复数字,则需要 Arrays.sort(nums);
backtracking(res, new ArrayList<Integer>(), nums, 0);
return res;
}
private void backtracking(ArrayList<List<Integer>> res, ArrayList<Integer> arr, int[] nums, int location){
if(nums==null || nums.length==0){
res.add(arr);
return;
}else{
res.add(new ArrayList<Integer>(arr));
for(int i=location; i<nums.length; i++){
// 如果有重复数字,则只调重复的第一个 if(i>location && nums[i]==nums[i-1]) continue;
arr.add(nums[i]);
backtracking(res, arr, nums, i+1);
arr.remove(arr.size()-1);
}
}
}
}

题目链接