java - 了解将数组切片为子数组的递归调用

Question

我发现这个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}, {}} 代码执行完毕后。

Answer 1

可以这样描述它正在做什么。

• 如果 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 是原始集合的大小。