Powerset (all subsets of a set) in Java

        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<E> it = set.iterator();
        while(it.hasNext()){
            Set<E> tmp = new HashSet<E>(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().

Like Peter already answered, you are adding the same subsets a lot (which are automatically removed since a Set cannot contain duplicates).

markspace solves this problem by using bit manipulations which is awesome, but might not be what you prefer. So I'll propose a different approach that uses the same general idea that you use, but optimised to not add doubles.

The main idea goes like this:

• Take 1 element out of the set
• find the powerset of the remaining elements.
• add all those subsets to the result
• add the element we removed to each of those subsets and add these new sets to the result as well

In code that would look like this:

public static <E> Set<Set<E>> findPowerSet(Set<E> set) {
    Set<E> result = new HashSet<>(set);
    return findPowerSetDestructive(result);
}

private static <E> Set<Set<E>> findPowerSetDestructive(Set<E> set){
    Set<Set<E>> ret = new HashSet<>();
    if(set.isEmpty()){
        ret.add(new HashSet<E>());
        return ret;
    }
    E current = set.iterator().next();
    set.remove(current);
    Set<Set<E>> subsets = findPowerSetDestructive(set);
    ret.addAll(subsets);
    for (Set<E> subset : subsets) {
        Set<E> newSubSet = new HashSet<E>(subset);
        newSubSet.add(current);
        ret.add(newSubSet);
    }
    return ret;
}

I added a helper method that literally takes out an element from the input set. That's why the original method copies the input set and starts off the destructive method with this safe copy. This way, we don't need to worry about the original input set being modified.

But can we do better? Like @markspace mentioned java doesn't really like recursive calls that much. Instead we can also build the result set from the ground up. The algorithm then becomes

• loop over all elements of the input set
• copy the power set we got from the previous elements
• add the current element to each of the sets in that power set
• add all those new sets to the result

Again, turning this into java code could look like this:

public static <E> Set<Set<E>> findPowerSet2(Set<E> set){
    Set<Set<E>> result = new HashSet<>();
    result.add(new HashSet<E>());
    for(E element : set){
        Set<Set<E>> previousSets = new HashSet<>(result);
        for (Set<E> subSet : previousSets) {
            Set<E> newSubSet = new HashSet<E>(subSet);
            newSubSet.add(element);
            result.add(newSubSet);
        }
    }
    return result;
}

It's good - but it's not object-oriented! All your methods are static and I guess that's fine but it's a procedural way of thinking. We can't instantiate a PowerSet (in fact, we can but it's useless). In your example, once you recieve your set of sets, the entire semantic that it's a powerset has been lost.

What would be better is if a PowerSet object was useful for something. Perhaps we could implement Set or Collection. I suggest we implement Iterable. Because it's easy and I'm lazy.

public class PowerSet<E> implements Iterable<Set<E>>
{
    private final Set<Set<E>> sets;

    public PowerSet(final Set<E> input)
    {
        sets = findPowerSet(input);
    }

    private static Set<Set<E>> findPowerSet(final Set<E> set)
    {
        // Identical to your code, but now private! (also made the param final)
    }

    public void print()
    {
        // Now non-static! Implement it yourself :)
    }

    public Iterator<Set<E>> iterator()
    {
        return sets.iterator(); // Just delegate to our set of sets
    }
}

Our PowerSet object is now useful! We can use it like this:

PowerSet<Character> pset = new PowerSet<>(set);
pset.print();

or

for(Set<Character> foo : pset)
{
    foo.toArray();
}

I would also go one step further and use Collections.unmodifiableSet to enforce that a user cannot modify the powerset, thereby invalidating it.

You could provide a method to return the original set, if you wanted.