题目要求
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
|
类似的题目有：
leetcode60 Permutation Sequence 可以参考这篇博客
leetcode77 Combinations 可以参考这篇博客
思路一：递归
还是利用递归的方式，在前一种情况的基础上遍历下一轮的组合情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
result.add(new ArrayList<Integer>());
subsets(result, nums, 0, new ArrayList<Integer>());
return result;
}
public void subsets(List<List<Integer>> result, int[] nums, int startIndex, List<Integer> currentList){
if(startIndex == nums.length){
return;
}
while(startIndex<nums.length){
currentList.add(nums[startIndex++]);
result.add(new ArrayList<Integer>(currentList));
subsets(result, nums, startIndex, currentList);
currentList.remove(currentList.size()-1);
}
}
|
思路2：排序后循环
起始subset集为：[]
添加S0后为：[], [S0]
添加S1后为：[], [S0], [S1], [S0, S1]
添加S2后为：[], [S0], [S1], [S0, S1], [S2], [S0, S2], [S1, S2], [S0, S1, S2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public List<List<Integer>> subsets(int[] S) {
List<List<Integer>> res = new ArrayList<>();
res.add(new ArrayList<Integer>());
for(int i : S) {
List<List<Integer>> tmp = new ArrayList<>();
for(List<Integer> sub : res) {
List<Integer> a = new ArrayList<>(sub);
a.add(i);
tmp.add(a);
}
res.addAll(tmp);
}
return res;
}
|