Generating all subsets of a given set

Question

I am learning Java Collections Framework. Can someone look at this code for generating all subsets of a given set and tell me any issues with it.

import java.util.*;
public class AllSubsets {
    public static void main(String[] args) {
        Set<Integer> original = new HashSet<Integer>();
        for (int i = Integer.parseInt(args[0]); i > 0; i--) {
            original.add(i);
        }   
        System.out.println(generateAllSubsets(original));
    }

    public static HashSet<HashSet<Integer>> generateAllSubsets(Set<Integer> original) {

        HashSet<HashSet<Integer>> allSubsets = new HashSet<HashSet<Integer>>();

        allSubsets.add(new HashSet<Integer>()); //Add empty set.

        Iterator it = original.iterator();
        while(it.hasNext()) {
            Integer element = (Integer) it.next();

            //Deep copy all subsets to temporary power set.
            HashSet<HashSet<Integer>> tempClone = new HashSet<HashSet<Integer>>();
            for (HashSet<Integer> subset : allSubsets) {
                tempClone.add((HashSet<Integer>)subset.clone());
            }       

            //All element to all subsets of the temporary power set.
            Iterator it2 = tempClone.iterator();
            while(it2.hasNext()) {
                Set<Integer> s = (HashSet<Integer>) it2.next();
                s.add(element);
            }   

            //Merge both power sets.
            allSubsets.addAll(tempClone);
        }   
        return allSubsets;
    }
}

Answer 1

The first, obvious, issue is that generating the set in memory uses a lot of memory. However, making a lazy version is a bit more advanced, so don't worry about it for now.

1. Code to the interface, not the implementation

public static HashSet<HashSet<Integer>> generateAllSubsets(Set<Integer> original) {

is bad.

public static Set<Set<Integer>> generateAllSubsets(Set<Integer> original) {

is better.

2. Generics reduce repetition

public static <T> Set<Set<T>> generateAllSubsets(Set<T> original) {

is better still, because you can use it to find power sets of any set.

3. Generics remove the necessity to do most casts

    Iterator it = original.iterator();
    while(it.hasNext()) {
        Integer element = (Integer) it.next();

and

        Iterator it2 = tempClone.iterator();
        while(it2.hasNext()) {
            Set<Integer> s = (HashSet<Integer>) it2.next();

have wholly unnecessary explicit casts (which in the second case generates a warning) because you're using the raw type Iterator. Both can also be simplified using the same foreach syntax which you use when making the copy of the power set so far.

4. KISS

You have three loops (including the one hidden behind allSubsets.addAll), which seems to me to be unnecessarily complicated. If you make a shallow copy first then you can combine the deep copy with the adding an element.

public static <T> Set<Set<T>> generateAllSubsets(Set<T> original) {
    Set<Set<T>> allSubsets = new HashSet<Set<T>>();

    allSubsets.add(new HashSet<T>()); //Add empty set.

    for (T element : original) {
        // Copy subsets so we can iterate over them without ConcurrentModificationException
        Set<Set<T>> tempClone = new HashSet<Set<T>>(allSubsets);

        // All element to all subsets of the current power set.
        for (Set<T> subset : tempClone) {
            Set<T> extended = new HashSet<T>(subset);
            extended.add(element);
            allSubsets.add(extended);
        }
    }

    return allSubsets;
}

You'll note that I'm using the copy-constructor rather than clone(). That's a matter of taste: fundamentally there's no real difference, because they're both special-cased.