Powerset (all subsets of a set) in Java I am trying to get a powerset (all subsets of a set) in Java. So my logic for that is:


A given set is one subset, so add so it as it is to result.
Remove each element of set from given set and we will get all the combinations for 1 element less. Add these results to final result.
Recursively find subsets of all sets from step 2 and add to result.


I tried searching for a similar solution on Stack Overflow but did not get one. Is this a clean way to implement it?

import java.util.*;

public class PowerSet {
    public static &lt;E&gt; Set&lt;Set&lt;E&gt;&gt; findPowerSet(Set&lt;E&gt; set){
        Set&lt;Set&lt;E&gt;&gt; ret = new HashSet&lt;Set&lt;E&gt;&gt;();
        ret.add(set);
        if(set.isEmpty()){
            return ret;
        }
        Iterator&lt;E&gt; it = set.iterator();
        while(it.hasNext()){
            Set&lt;E&gt; tmp = new HashSet&lt;E&gt;(set);   //create a copy of current set
            tmp.remove(it.next());              //remove current element from copy set
            ret.add(tmp);                       //add the remaining set to result
            ret.addAll(findPowerSet(tmp));      //recursively find subsets of copy set
        }
        return ret;
    }

    public static void main(String[] args) {
        Set&lt;Character&gt; set = new HashSet&lt;Character&gt;();
        set.add('a');set.add('b');set.add('c');
        System.out.println("Input set");        printSet(set);
        System.out.println("\nsub sets");
        findPowerSet(set).stream().forEach(PowerSet::printSet);
    }

    public static &lt;E&gt; void printSet(Set&lt;E&gt; set){
        StringBuilder sb = new StringBuilder(set.size()==0 ? "{}\n" :"{");
        Iterator&lt;E&gt; it = set.iterator();
        while(it.hasNext()){
            sb.append(it.next().toString())
            .append(it.hasNext()? ", " : "}\n");
        }
        System.out.print(sb.toString());
    }
}
if(set.isEmpty()){
            return ret;
        }



This is unnecessary. If the set is empty, the iterator will return false to the first hasNext(), and you'll go straight to the final return ret;.

Other than that, it seems like a simple, obviously correct, approach.

However, it is quite inefficient.

        Iterator&lt;E&gt; it = set.iterator();
        while(it.hasNext()){
            Set&lt;E&gt; tmp = new HashSet&lt;E&gt;(set);   //create a copy of current set
            tmp.remove(it.next());              //remove current element from copy set
            ret.add(tmp);                       //add the remaining set to result
            ret.addAll(findPowerSet(tmp));      //recursively find subsets of copy set
        }
        return ret;
    }


Suppose that we call it with a set of \$n\$ elements. The outermost call produces a set of \$2^n\$ subsets by taking the union of \$n\$ subresults, each of \$2^{n-1}\$ elements. So the outermost call discards as duplicates \$(n-2)2^{n-1}\$ subsets. But, of course, each of those recursive calls discarded \$(n-3)2^{n-2}\$ subsets from their subresults, etc.

This is why the typical simple implementation is to build up from the empty set.

An advanced implementation, which isn't always better but can reduce copying in some use cases, is to write a custom iterator which uses a Gray code to add or remove precisely one element in each call to next().