题目描述
给定一个含不同整数的集合，返回其所有的子集，子集中的元素排列必须是非降序的，解集必须不包含重复的子集
思路
对含有n个不同元素的集合，其子集有2^n种。
对每一个元素，只有两种情况：包含与不包含。假设包含用1表示，不包含用0表示，那这n个元素就可以排列成一个二进制数，而数的范围恰巧就是0~2^n - 1
二进制0和1就代表了两种情况，所以每一个子集必然对应一个二进制数
所以可以通过逆向的思路求解子集：
对在0~2^n -1的每个数 i，求其对应的二进制数，用数组a保存结果。
访问数组a的每一个元素，如果不为0，该位置对应的集合中的元素加入list
例：对集合[1,2,3]，其对应的值的范围在0~7
当i=6时，其二进制为110，则将1、2加入到list，再将list加入到listHolder即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| private ArrayList<ArrayList<Integer>> listHolder;
public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
// 子集非降序，那我先按升序排一遍
Arrays.sort(nums);
// 添加第i位，则addOrNot[i]=1,否则为0
int[] addOrNot = new int[nums.length];
listHolder = new ArrayList<ArrayList<Integer>>();
int count = getCount(nums.length);
// 遍历0~2^num.length-1，根据当前值i，构造addOrNot数组（存储i的二进制表示），输出一种子集，遍历完得到所有子集
for(int i = 0; i < count; i++) {
int tmpNum = i;
for(int j = nums.length-1; j >=0; j--) {
addOrNot[j] = tmpNum / getCount(j);
tmpNum %= getCount(j);
}
// 访问addOrNot，将值为1指向的元素添加到List
ArrayList<Integer> list = new ArrayList<>();
for(int k = 0; k < addOrNot.length; k++) {
if(addOrNot[k] == 1) {
list.add(nums[k]);
}
}
listHolder.add(list);
}
return listHolder;
}
private int getCount(int n) {
int res = 1;
for(int i = 0; i < n; i++) {
res *= 2;
}
return res;
}
|
考察点