Career cup 9.4

AllSubsets.java

package Chapter9;

import java.util.ArrayList;

public class AllSubsets {
    
    //Iterative way
    public static ArrayList<ArrayList<Integer>> getAllSubsets(ArrayList<Integer> set) {
	ArrayList<ArrayList<Integer>> allSubsets = new ArrayList<ArrayList<Integer>>();
	allSubsets.add(new ArrayList<Integer>());//empty set
	
	for(int i = 0; i < set.size(); i++) {
	    int elem = set.get(i);
	    ArrayList<ArrayList<Integer>> newSubsets = new ArrayList<>();
	    for (ArrayList<Integer> subset : allSubsets) {
		ArrayList<Integer> newSubset = new ArrayList<>();
		newSubset.addAll(subset);
		newSubset.add(elem);
		newSubsets.add(newSubset);
	    }
	    
	    allSubsets.addAll(newSubsets);
	}
	
	return allSubsets;
    }
    
    //Binary presentation
    public static ArrayList<ArrayList<Integer>> getAllSubsets2(ArrayList<Integer> set) {
	ArrayList<ArrayList<Integer>> allSubsets = new ArrayList<>();
	int n = 1;
	for(int i = 0; i < set.size(); i++) {
	    n *= 2;
	}
	
	for(int i = 0; i < n; i++) {
	    allSubsets.add(transfer(i, set));
	}
	return allSubsets;
    }
    
    
    private static ArrayList<Integer> transfer(int k, ArrayList<Integer> set) {
	ArrayList<Integer> subset = new ArrayList<>();
	int i = 0;
	while(k > 0) {
	    boolean inSet = (k & 1) == 1;
	    if(inSet)
		subset.add(set.get(i));
	    i++;
	    k >>= 1;
	}
	return subset;
    }

    //helper function t print all subsets
    public static void printSets(ArrayList<ArrayList<Integer>> sets) {
	int i = 1;
	for (ArrayList<Integer> set : sets) {
	    System.out.print("Set " + i + ": ");
	    for (Integer elem : set) {
		System.out.print(elem + " ");
	    }
	    System.out.println();
	    i++;
	}
    }
    
    public static void main(String[] args) {
	ArrayList<Integer> set = new ArrayList<Integer>();
	for(int i = 0; i < 5; i++) {
	    set.add(i);
	}
	
	printSets(getAllSubsets2(set));
    }
}