在Java中获取集合的幂集

在Java中获取集合的幂集

是的，

O(2^n)

的确如此，因为你需要生成

2^n

可能的组合。这是一个使用泛型和集合的有效实现：

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;}  

根据你的示例输入进行测试：

 Set<Integer> mySet = new HashSet<Integer>(); mySet.add(1); mySet.add(2); mySet.add(3); for (Set<Integer> s : SetUtils.powerSet(mySet)) {     System.out.println(s); }