super set by bit array

By | October 20, 2015
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

This is my try for super set problem given by junmin link.
Given a set of unique characters, generate its superset. example: a, b, c, its superset are:
[[], [c], [b], [c, b], [a], [c, a], [b, a], [c, b, a]]

Normal way is to use recursion. But another way is to use bit array. For {a, b, c}, 001 represents {c}, 110 represents {a, b}. In this way, all we need is to iterate a number from 000 to 111 to get all sets.

/**
 * Created by lipeng on 2015/5/15.
 */
public class SuperSet {
    public static void main(String[] args) {
        char[] chs = {'a', 'b', 'c', 'd'};
        printSuperSet(chs);
    }

    public static void printSuperSet(char[] chs) {
        List<List<Character>> sets = new ArrayList<List<Character>>();
        int size = (int)Math.pow(2, chs.length);
        for(int i=0; i<size; i++) {
            List<Character> list = new ArrayList<Character>();
            for(int j=0; j<chs.length; j++) {
                if(((1<<j)&i)>0) {
                    list.add(chs[j]);
                }
            }
            sets.add(list);
        }
        System.out.println(sets);
    }

}