Interview Question for Software Engineer at Google:

How about something like this? Running time is O(n!).

(Java)
    /**
     * The power set of S is the set of all subsets of S, including the empty
     * set and S itself. It is parallel to the idea of all combinations of
     * characters in a string.
     */
    public Set<Set<Object>> getPowerSet(Set<Object> s){
        Set<Set<Object>> pset = new HashSet<Set<Object>>();

        Object[] a = s.toArray();

        // Add the empty set
        Set<Object> subset = new HashSet<Object>();
        pset.add(new HashSet<Object>(subset));

        int n = s.size();
        this.getPset(a,subset,pset,n,0);
        return pset;
    }

    private void getPset(Object[] a, Set<Object> subset, Set<Set<Object>> pset, int originalSize, int currentSize){
        for (int i = currentSize; i < originalSize; i++){
            subset.add(a[i]);
            System.out.println("Attempting to add " + subset + ". i = " + i);
            pset.add(new HashSet<Object>(subset));
            if (i < originalSize - 1){
                getPset(a,subset,pset,originalSize,i+1);
            }
            subset = new HashSet<Object>();
        }
    }

That's a clever way to do it! Though good look thinking that up on the spot.

What i did was, assuming the set has n elements:
for (i; from 0; to (2^n)-1)
{
    generate binary represenation of i padded to n bits. (e.g if n=8, and i =4, representation would be 00100000). Call this representation "bitmap"

   for (j; from 0; to bitmap.length)
{
        if bitmap[j]==1: add set[j] to a tempset
}
add tempset to a global array of sets

}
return that global array of sets

Note that this has exponential complexity which i believe (but am not sure) is better than factorial complexity

OP, I think yours is better, and easier to understand too. :)

O(n*2^n) is better than O(n!) as n grows.

Thanks for posting the question.

Here's the Java version of your algorithm if you don't want to explicitly pad:

    Set powerset(Set set) {

        Set power = new HashSet();
        Object[] a = set.toArray();
        int n = a.length;
        int maxCount = (int)Math.pow(2,n);
        for (int i = 0; i < maxCount; i++){
            Set subset = new HashSet();
            char[] c = Integer.toBinaryString(i).toCharArray();
            int m = c.length;
            for (int j = m-1; j >= 0; j--){
                if (c[j] == '1') {
                    subset.add(a[(n-1)-(m-1-j)]);
                }
            }
            power.add(subset);
        }

        return power;
    }

Using recursion and run in O(n2^n).

public List<List<Integer>> powerset(final List<Integer> set) {
        // If set is empty, just return an empty powerset.
        if(set.isEmpty()) return new ArrayList<List<Integer>>();
        // Pop the first element as a candidate for composition.
        final Integer i = set.remove(0);
        // Get powerset of the set without the candidate.
        final List<List<Integer>> subset = this.powerset(set);
        // If the returned powerset is empty, add an empty set to it.
        if(subset.isEmpty()) {
            subset.add(new ArrayList<Integer>());
        }
        // For all the existing sets in the powerset without the candidate,
        // add the all combination sets of existing sets plus the candidate
        // to the powerset.
        final int length = subset.size();
        for(int j = 0; j < length; j++) {
            final List<Integer> s = subset.get(j);
            final List<Integer> sWithi = new ArrayList<Integer>(s);
            sWithi.add(i);
            subset.add(sWithi);
        }
        return subset;
    }

I finally got my head around a clearer version... credits to John Mongan et al:

public Set getPowerset(Set set) {
    Set powerset = new HashSet();
    powerset.add(new HashSet()); // Add the empty set
    getPset(set.toArray(), new HashSet(), powerset, set.size(), 0);
    return powerset;
}

private void getPset(Object[] input, Set subset, Set powerset, int n, int start) {
    for (int i = start; i < n; i++) {
        Object o = input[i];
        subset.add(o);
        powerset.add(new HashSet(subset));
        if ( i < n-1) {
            getPset(input, subset, powerset, n, i+1);
        }
        subset.remove(o);
    }
}

Time for n = 16 for binary version: 10089 ms. Items: 65536.
Time for n = 16 for recursive version: 9379 ms. Items: 65536

ellemeno dude if you don't ace your google interview, I'm going to be very disappointed :)

Good luck!