没有递归的一种方法是：使用二进制掩码并进行所有可能的组合。

public HashSet<HashSet> createPowerSet(Object[] array)
{
    HashSet<HashSet> powerSet=new HashSet();
    boolean[] mask= new boolean[array.length];

    for(int i=0;i<Math.pow(2, array.length);i++)
    {
        HashSet set=new HashSet();
        for(int j=0;j<mask.length;j++)
        {
            if(mask[i])
                set.add(array[j]);
        }
        powerSet.add(set);      

        increaseMask(mask);
    }

    return powerSet;
}

public void increaseMask(boolean[] mask)
{
    boolean carry=false;

    if(mask[0])
        {
            mask[0]=false;
            carry=true;
        }
    else
        mask[0]=true;

    for(int i=1;i<mask.length;i++)
    {
        if(mask[i]==true && carry==true)
        mask[i]=false;
        else if (mask[i]==false && carry==true)
        {
            mask[i]=true;
            carry=false;
        }
        else 
            break;

    }

}

我在寻找一个解决方案，它不像这里贴的那么大。这是针对Java7的，因此对于版本5和版本6，它将需要少量的粘贴。

Set<Set<Object>> powerSetofNodes(Set<Object> orig) {
    Set<Set<Object>> powerSet = new HashSet<>(),
        runSet = new HashSet<>(),
        thisSet = new HashSet<>();

    while (powerSet.size() < (Math.pow(2, orig.size())-1)) {
        if (powerSet.isEmpty()) {
            for (Object o : orig) {
                Set<Object> s = new TreeSet<>();
                s.add(o);
                runSet.add(s);
                powerSet.add(s);
            }
            continue;
        }
        for (Object o : orig) {
            for (Set<Object> s : runSet) {
                Set<Object> s2 = new TreeSet<>();
                s2.addAll(s);
                s2.add(o);
                powerSet.add(s2);
                thisSet.add(s2);
            }
        }
        runSet.clear();
        runSet.addAll(thisSet);
        thisSet.clear();
    }
    powerSet.add(new TreeSet());
    return powerSet;

下面是一些要测试的示例代码：

Set<Object> hs = new HashSet<>();
hs.add(1);
hs.add(2);
hs.add(3);
hs.add(4);
for(Set<Object> s : powerSetofNodes(hs)) {
    System.out.println(Arrays.toString(s.toArray()));
}

是的，是的 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);
 }

这是我对兰博达斯的态度。

public static <T> Set<Set<T>> powerSet(T[] set) {
      return IntStream
            .range(0, (int) Math.pow(2, set.length))
            .parallel() //performance improvement
            .mapToObj(e -> IntStream.range(0, set.length).filter(i -> (e & (0b1 << i)) != 0).mapToObj(i -> set[i]).collect(Collectors.toSet()))
            .map(Function.identity())
            .collect(Collectors.toSet());
        }

或并行（请参见parallel（）注解）：
输入集大小：18
逻辑处理器：8à 3.4兆赫
性能提升：30%

这里有一个解决方案，我使用一个发电机，优点是，整个发电机组从来没有存储在一次。。。所以你可以一个接一个地迭代它，而不需要把它存储在内存中。我想这是个更好的选择。。。注意复杂性是相同的，o（2^n），但是内存需求减少了（假设垃圾收集器的行为是！；）

/**
 *
 */
package org.mechaevil.util.Algorithms;

import java.util.BitSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

/**
 * @author st0le
 *
 */
public class PowerSet<E> implements Iterator<Set<E>>,Iterable<Set<E>>{
    private E[] arr = null;
    private BitSet bset = null;

    @SuppressWarnings("unchecked")
    public PowerSet(Set<E> set)
    {
        arr = (E[])set.toArray();
        bset = new BitSet(arr.length + 1);
    }

    @Override
    public boolean hasNext() {
        return !bset.get(arr.length);
    }

    @Override
    public Set<E> next() {
        Set<E> returnSet = new TreeSet<E>();
        for(int i = 0; i < arr.length; i++)
        {
            if(bset.get(i))
                returnSet.add(arr[i]);
        }
        //increment bset
        for(int i = 0; i < bset.size(); i++)
        {
            if(!bset.get(i))
            {
                bset.set(i);
                break;
            }else
                bset.clear(i);
        }

        return returnSet;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not Supported!");
    }

    @Override
    public Iterator<Set<E>> iterator() {
        return this;
    }

}

要调用它，请使用以下模式：

Set<Character> set = new TreeSet<Character> ();
        for(int i = 0; i < 5; i++)
            set.add((char) (i + 'A'));

        PowerSet<Character> pset = new PowerSet<Character>(set);
        for(Set<Character> s:pset)
        {
            System.out.println(s);
        }

它来自我的项目库…：）

下面是一个教程，详细描述了您想要的内容，包括代码。你是对的，复杂性是o（2^n）。

t的子集是通过去掉t的零个或多个元素而形成的任何集合。withoutfirst子集将t中缺少第一个元素的子集相加，for循环将处理将子集与第一个元素相加的问题。例如，如果t包含元素[“1”、“2”、“3”]，missingfirst将添加[[“”]、[“2”]、[“3”]、[“2”、“3”]]，for循环将在这些元素前面粘贴“1”，并将其添加到newset。因此，我们将以[[“”]，[“1”]，[“2”]，[“3”]，[“1”，“2”]，[“1”，“3”]，[“2”，“3”]，[“1”，“2”，“3”]。

public static Set<Set<String>> allSubsets(Set<String> t) {
        Set<Set<String>> powerSet = new TreeSet<>();
        if(t.isEmpty()) {
            powerSet.add(new TreeSet<>());
            return powerSet;
        }
        String first = t.get(0);
        Set<Set<String>> withoutFirst = allSubsets(t.subSet(1, t.size()));
        for (List<String> 1st : withoutFirst) {
            Set<String> newSet = new TreeSet<>();
            newSet.add(first);
            newSet.addAll(lst);
            powerSet.add(newSet);
        }
        powerSet.addAll(withoutFirst);
        return powerSet;
    }

如果您使用的是eclipse集合（以前称为gs集合），那么可以使用 powerSet() 所有可设置项上的方法。

MutableSet<Integer> set = UnifiedSet.newSetWith(1, 2, 3);
System.out.println("powerSet = " + set.powerSet());
// prints: powerSet = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

注意：我是eclipse集合的提交者。

如果n<63，这是一个合理的假设，因为无论如何都要尝试构造幂集时内存不足（除非使用迭代器实现），这是一种更简洁的方法。二进制运算比 Math.pow() 和数组的掩码，但不知何故java用户害怕他们。。。

List<T> list = new ArrayList<T>(originalSet);
int n = list.size();

Set<Set<T>> powerSet = new HashSet<Set<T>>();

for( long i = 0; i < (1 << n); i++) {
    Set<T> element = new HashSet<T>();
    for( int j = 0; j < n; j++ )
        if( (i >> j) % 2 == 1 ) element.add(list.get(j));
    powerSet.add(element); 
}

return powerSet;

实际上，我已经编写了一些代码来满足您在o（1）中的要求。问题是你下一步打算怎么处理这台电视机。如果你要打电话 size() 在它上面，这是o（1），但是如果你要迭代它，那显然是 O(2^n) . contains() 会是 O(n) 等等。
你真的需要这个吗？
编辑：
这段代码现在在guava中可用，并通过该方法公开 Sets.powerSet(set) .

我最近不得不使用这样的东西，但是首先需要最小的子列表（有1个元素，然后是2个元素，…）。我不想把空的也不想把整张单子都包括进去。而且，我不需要返回所有子列表的列表，我只需要对每个子列表做一些处理。
希望不使用递归实现这一点，并提出了以下建议（将“正在做的事情”抽象为一个函数接口）：

@FunctionalInterface interface ListHandler<T> {
    void handle(List<T> list);
}

public static <T> void forAllSubLists(final List<T> list, ListHandler handler) {
    int     ll = list.size();   // Length of original list
    int     ci[] = new int[ll]; // Array for list indices
    List<T> sub = new ArrayList<>(ll);  // The sublist
    List<T> uml = Collections.unmodifiableList(sub);    // For passing to handler

    for (int gl = 1, gm; gl <= ll; gl++) {  // Subgroup length 1 .. n-1
        gm = 0; ci[0] = -1; sub.add(null);  // Some inits, and ensure sublist is at least gl items long

        do {
                ci[gm]++;                       // Get the next item for this member

                if (ci[gm] > ll - gl + gm) {    // Exhausted all possibilities for this position
                        gm--; continue;         // Continue with the next value for the previous member
                }

                sub.set(gm, list.get(ci[gm]));  // Set the corresponding member in the sublist

                if (gm == gl - 1) {             // Ok, a sublist with length gl
                        handler.handle(uml);    // Handle it
                } else {
                        ci[gm + 1] = ci[gm];    // Starting value for next member is this 
                        gm++;                   // Continue with the next member
                }
        } while (gm >= 0);  // Finished cycling through all possibilities
    }   // Next subgroup length
}

这样，也很容易将其限制为特定长度的子列表。

当集合的大小很大时，上面的一些解决方案会受到影响，因为它们会创建大量要收集的对象垃圾，并且需要复制数据。我们怎样才能避免呢？我们可以利用这样一个事实，即我们知道结果集的大小将有多大（2^n），预先分配一个那么大的数组，然后只附加到它的末尾，从不复制。
加速比随n的增加而迅速增大。我把它比作乔ão席尔瓦的解决方案。在我的机器上（所有测量值都是近似值），n=13快5倍，n=14快7倍，n=15快12倍，n=16快25倍，n=17快75倍，n=18快140倍。因此，垃圾创建/收集和复制在其他类似的big-o解决方案中占主导地位。
与让数组动态增长相比，在开始时预分配数组似乎是一种胜利。当n=18时，动态增长所需的时间大约是整体增长的两倍。

public static <T> List<List<T>> powerSet(List<T> originalSet) {
    // result size will be 2^n, where n=size(originalset)
    // good to initialize the array size to avoid dynamic growing
    int resultSize = (int) Math.pow(2, originalSet.size());
    // resultPowerSet is what we will return
    List<List<T>> resultPowerSet = new ArrayList<List<T>>(resultSize);

    // Initialize result with the empty set, which powersets contain by definition
    resultPowerSet.add(new ArrayList<T>(0)); 

    // for every item in the original list
    for (T itemFromOriginalSet : originalSet) {

        // iterate through the existing powerset result
        // loop through subset and append to the resultPowerset as we go
        // must remember size at the beginning, before we append new elements
        int startingResultSize = resultPowerSet.size();
        for (int i=0; i<startingResultSize; i++) {
            // start with an existing element of the powerset
            List<T> oldSubset = resultPowerSet.get(i);

            // create a new element by adding a new item from the original list
            List<T> newSubset = new ArrayList<T>(oldSubset);
            newSubset.add(itemFromOriginalSet);

            // add this element to the result powerset (past startingResultSize)
            resultPowerSet.add(newSubset);
        }
    }
    return resultPowerSet;
}

算法：
输入：设置[]，设置大小1。获取幂集powet\ U set\ U size=pow（2，set\ U size）2循环的大小，计数器从0到pow\ U set\ U size（a）循环i=0到set\ U size（i），如果计数器中的第i位被设置，则打印该子集集合中的第i个元素（b）打印子集合的分隔符，即换行符

# include <stdio.h>

# include <math.h>

void printPowerSet(char *set, int set_size)
{
    /*set_size of power set of a set with set_size
      n is (2**n -1)*/
    unsigned int pow_set_size = pow(2, set_size);
    int counter, j;

    /*Run from counter 000..0 to 111..1*/
    for(counter = 0; counter < pow_set_size; counter++)
    {
      for(j = 0; j < set_size; j++)
       {
          /* Check if jth bit in the counter is set
             If set then pront jth element from set */
          if(counter & (1<<j))
            printf("%c", set[j]);
       }
       printf("\n");
    }
}

/*Driver program to test printPowerSet*/
int main()
{
    char set[] = {'a','b','c'};
    printPowerSet(set, 3);

    getchar();
    return 0;
}

下面是一个简单的迭代o（2^n）解：

public static Set<Set<Integer>> powerSet(List<Integer> intList){

    Set<Set<Integer>> result = new HashSet();
    result.add(new HashSet());

    for (Integer i : intList){

        Set<Set<Integer>> temp = new HashSet();

        for(Set<Integer> intSet : result){

            intSet = new HashSet(intSet);
            intSet.add(i);                
            temp.add(intSet);
        }
        result.addAll(temp);
    }
    return result;
}

public class PowerSet {
    public static List<HashSet<Integer>> powerset(int[] a) {
        LinkedList<HashSet<Integer>> sets = new LinkedList<HashSet<Integer>>();
        int n = a.length;
        for (int i = 0; i < 1 << n; i++) {
            HashSet<Integer> set = new HashSet<Integer>();
            for (int j = 0; j < n; j++) {
                if ((1 << j & i) > 0)
                    set.add(a[j]);
            }
            sets.add(set);
        }
        return sets;
    }

    public static void main(String[] args) {
        List<HashSet<Integer>> sets = PowerSet.powerset(new int[]{ 1, 2, 3 });
        for (HashSet<Integer> set : sets) {
            for (int i : set)
                System.out.print(i);
            System.out.println();
        } 
    }
}