Power Set: Write a method to return all subsets of a set.
Hints: #273, #290, #338, #354, #373
解法1
时间复杂度估算**（很重要，这个是答案里说的）**：
我们返回一个集合的所有子集，比如{1, 2, 3}的子集是{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}，那么所有子集的元素数量之和就是我们的时间复杂度（同时也是空间复杂度）。为什么？因为元素数量就是List.add的调用次数啊。
那么所有子集的元素数量之和怎么算出来？
先看会有多少个子集，每个元素要么出现在子集中，要么不出现在子集中，所以每个元素都有两种可能，那么子集的数量等于2 * 2 * 2 ..，也就是2n个（上面的例子是7个是因为去掉了空集）。
每个元素出现在某个子集里的机会是1/2，也就是说对于每个元素来说，一半的子集里有它。因此所有子集的元素数量之和等于n * 2n - 1个。
因此时间复杂度：O(n * 2n)
空间复杂度：O(n * 2n)
- P(N)记为，N个元素的所有子集
- P(N) = P(N - 1) + 取出的元素 | P(N - 1)。意思是P(N)的子集等于：P(N - 1)的所有子集，加上，把某个被取出的元素加入到所有P(N - 1)的子集里形成的新的子集。
- P(0) = 空集
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public List<List<Integer>> powerSets(List<Integer> set, int index) {
List<List<Integer>> subsets;
if (index == set.size()) {
subsets = new ArrayList<>();
subsets.add(new ArrayList<>());
return subsets;
}
subsets = powerSets(set, index + 1);
Integer element = set.get(index);
List<List<Integer>> newSubsets = new ArrayList<>();
for (List<Integer> subSubset : subsets) {
List<Integer> clonedSubSubset = new ArrayList<>(subSubSet);
clonedSubSubset.add(element);
newSubsets.add(clonedSubSubset);
}
subsets.addAll(newSubsets);
return subsets;
}
|
解法2
前面已经提到了在某个子集中，某个元素要么出现要么不出现，那么这个就能够想到二进制，出现用1表示，不出现用0表示，那么我们可以遍历0～2n（不含）的数字，然后根据其二进制形式来构建子集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public List<List<Integer>> powerSets(List<Integer> set) {
int max = Math.power(2, set.size());
List<List<Integer>> results = new ArrayList<>();
for (int i = 0; i < max; i++) {
results.add(translateBinary(i, set));
}
return results;
}
public List<Integer> translateBinary(int num, List<Integer> set) {
List<Integer> result = new ArrayList<>();
int index = 0;
while (num != 0) {
if (num & 1 == 1) {
result.add(set.get(index));
}
index++;
num >>= 1;
}
return result;
}
|
评论