java - 获取列表的 Powerset 的最佳方法(递归)

Question

为了获取列表的幂集，我实现了以下内容:

public static ArrayList<ArrayList<Integer>> getAllSubsets(ArrayList<Integer> set, int index, ArrayList<Integer> subset){
    ArrayList<ArrayList<Integer>> subsets = new ArrayList<ArrayList<Integer>>();

    if(index == set.size()){
        subsets.add(new ArrayList<Integer>(subset));
        return subsets;
    }

    subsets.addAll(getAllSubsets(set, index + 1, subset));
    subset.add(set.get(index));
    subsets.addAll(getAllSubsets(set, index + 1, subset));
    subset.remove(subset.size()-1);
    return subsets;
}

这是使用递归获取列表幂集的最佳方法吗？我在互联网上看到了很多关于如何实现这一点的不同方法，但他们似乎比我的复制(使用新的)更多。

例如，这个 StackOverlow post在我的谷歌搜索中出现，但他的实现(Joao Silva)使用了大量的复制，并且似乎不是最佳的。然而，我经常看到他的实现，这让我感到困惑。该实现比我正在使用的实现更好(当然，除了他使用泛型这一事实之外)？

他的代码:

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
    Set<Set<T>> sets = new HashSet<Set<T>>();
    if (originalSet.isEmpty()) {
        sets.add(new HashSet<T>());
        return sets;
    }
    List<T> list = new ArrayList<T>(originalSet);
    T head = list.get(0);
    Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
    for (Set<T> set : powerSet(rest)) {
        Set<T> newSet = new HashSet<T>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }       
    return sets;
}

Answer 1

您可能会找到这个page有用。它包含以各种语言并使用不同方法实现的 powerset。对于 Java，有以下三种方法:

1. 迭代
2. 递归
3. 并使用二进制字符串

其实我最喜欢第三种方式，因为里面的想法很好。不同之处在于，他们假设输入是一个字符串。

顺便说一句。如果它将是在生产中使用的任何代码，我宁愿避免使用递归，因为堆栈可能存在问题(不幸的是，Java 中仍然不支持尾递归)