Subsets

Question: Find all subsets of the set {‘foo’, ‘bar’, baz’}.  The method signature for the solution should be

public List<HashSet<String>> findSubsets(Set<String> input)

Evaluation: There is a fairly clever way to solve this that will run in O(2^n) which by the way is the fastest solution available for this question.  There is a more obvious but also slower solution that runs in something more like O((2^n)^2).

To get to the faster version of the solution consider how many subsets there are.  The naive solution comes from the recognition that if you start with the empty set {} and then for each element in the list of sets so far you create 1 new set for every existing set by adding the new element to every existing set.

-> {}

-> {‘foo’}

-> {‘bar’}, {‘foo’, ‘bar’}

-> {‘baz’}, {‘foo’, ‘baz’}, {‘bar’, ‘baz’}, {‘foo’, ‘bar’, ‘baz’}

When you put all of these together there are a total of 8 subsets.  The key here is to recognize that there are 2^n subsets in the solution.  The next thing to remember is that 2^n is binary.  Now, try counting from 0-2^n in binary (in this case 0-8).

000

001

010

011

100

101

110

111

Do you see a solution emerging?  If you take the binary representation of every number from 0 – 2^n you get 1 unique set at each index.

Code:

public List<HashSet<String>> findSubsets(Set<String> input) {
        LinkedList<HashSet<String>> result = new LinkedList<HashSet<String>>();
        LinkedList<String> list = new LinkedList<String>();
        list.addAll(input);
        int numsubsets = (int)Math.pow(2, input.size());
        for(int i=0;i<numsubsets;i++) {
            int current = i;
            int index = 0;
            HashSet set = new HashSet();
            result.add(set);
            while(current != 0) {
                if(current % 2 !=0) {
                    set.add(list.get(index));
                }
                index++;
                current = current >>> 1;
            }
        }

        return result;
    }