我发现这个java代码片段将数组分割成它的所有子集。但我无法理解递归调用是如何工作的以及子集是如何形成的。对集合 {1,2,3} 的解释会非常有帮助。提前致谢!
public static Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
Set<Set<Integer>> sets = new HashSet<Set<Integer>>(); //All the subsets will be stored in sets.
if (originalSet.isEmpty()) {
sets.add(new HashSet<Integer>());
return sets;
}
List<Integer> list = new ArrayList<Integer>(originalSet);
int head = list.get(0);
Set<Integer> rest = new HashSet<Integer>(list.subList(1, list.size()));
for (Set<Integer> set : powerSet(rest)) {
Set<Integer> newSet = new HashSet<Integer>();
newSet.add(head);
newSet.addAll(set);
sets.add(newSet);
sets.add(set);
}
return sets;
}
sets 本身是一个集合,它包含 {{1},{1,2},{1,3},{2,3},{2},{3},{1,2,3}, {}} 代码执行完毕后。
最佳答案
可以这样描述它正在做什么。
- 如果 OriginalSet 为空,则返回
{}
(因为空集的唯一子集就是空集)。 - 将 OriginalSet 拆分为第一个元素 (
head
) 和所有其他元素 (rest
)。 - 我们正在维护一个正在运行的集合(
集合
),这最终将成为我们的答案。对于原始集的每个不包含第一个元素的子集(rest
的子集),将其和包含其所有元素以及head
的集合放入我们的集合中。
{1, 2, 3}
示例:
We want to find the power set of {1, 2, 3}.
In order to do this, we take off 1 and find the power set of {2, 3}.
In order to do this, we take off 2 and find the power set of {3}.
In order to do this, we take off 3 and find the power set of {}.
Which is {}.
For everything above ({}), copy it over, then copy it over but add a 3.
We have {{}, {3}}.
For everything above ({}, {3}), copy it over, then copy it over but add a 2.
We have {{}, {3}, {2}, {2, 3}}.
For everything above ({}, {3}, {2}, {2, 3}), copy it over, then copy it over but add a 1.
We have {{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}}.
请注意,应该始终有 2^n
个元素,其中 n
是原始集合的大小。
关于java - 了解将数组切片为子数组的递归调用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23600700/