求 {1,2,3} 幂集的算法

Question

我觉得这有点令人困惑，因为我从未真正使用过 Java 集。有人可以尝试向我展示以下代码（最好是通过解释幂集是如何逐渐创建的）（PS 我从 stackoverflow 上的帖子中获得了此代码，所以功劳归于那个人）：

public static void main(String[] args) {
        Set<Integer> mySet = new HashSet<Integer>();
        mySet.add(1);
        mySet.add(2);
        mySet.add(3);
        for (Set<Integer> s : powerSet(mySet)) {
            System.out.println(s);
        }

    }

    public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
        Set<Set<T>> sets = new HashSet<Set<T>>();

        //If the input is empty, add the empty set and return
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<T>());
            return sets;
        }

        //Put the originalSet into an arraylist
        List<T> list = new ArrayList<T>(originalSet);

        //Get the first element
        T head = list.get(0);

        //Get everything but the first element and put into a set
        Set<T> rest = new HashSet<T>(list.subList(1, list.size()));

        //For each element in the set above
        for (Set<T> set : powerSet(rest)) {

            //Create a new set
            Set<T> newSet = new HashSet<T>();

            //Add the head
            newSet.add(head);

            //Add the rest
            newSet.addAll(set);

            //Add all of newset to the result
            sets.add(newSet);

            //Add the current element
            sets.add(set);
        }
        return sets;
    }

Answer 1

考虑 {1, 2, 3} 的幂集。我们可以将其视为以下组合：

{}  
{1} + powerset {2, 3}  
{2} + powerset {3}  
{3} + powerset {}

采用 {1} + powerset {2, 3} 行，这会扩展为：

{1} + { {}, {2}, {3}, {2, 3} }

进而变为：

{ {1}, {1, 2}, {1, 3}, {1, 2, 3} }

代码执行相同的操作，使用递归来生成较小的幂集并将每个幂集累积到列表中。