Given a set of characters. Find the power set or super set of the set.

For example, S={a,b,c}, then powerSet = {{}, {a}, {b}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c}}.

For a set of n elements there are 2^n elements on the super set including the empty set. The brute-force method would be to find all possible combinations of the elements using 0, 1, 2,…n elements. But that will have an exponential time al? complexity. How can we do it in less than exponential?

Notice that, if we represent each unique letters by a bit position in a n bit integer than the power set will look like, for example for n=3,

{}    ->  000
{a}   ->  001
{b}   ->  010
{c}   ->  100
{a, b} -> 011
{b, c} -> 110
{a, c} -> 101
{a,b,c}-> 111

That is we can generate the power set of n numbers by looking at the bit positions n bit integers. So, we will basically take each integer from 0 to 2^n-1 and for each we will check the bit positions set. Each number corresponds to a set in the superset and each set bit position will contribute to an element in the set. Below is the implementation of this idea which runs in O(n*2^n) time and O(1) space.

public static List<List<Character>> powerSet(char[] chars){
	int n = chars.length;
	List<List<Character>> powerSet = new ArrayList<List<Character>>();
	//superSet.add(Collections.emptyList());
	
	if(n == 0){
		return powerSet;
	}
	
	int max = (int)Math.pow(2, n);
	for(int i = 0; i<max; i++){
		List<Character> set = new ArrayList<Character>();
		for(int j = 0; j<n; j++){
			if((i & (1<<j)) > 0){
				set.add(chars[j]);
			}
		}
		powerSet.add(set);
	}
	
	return powerSet;
}