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);
}
}
