CTCI 9.4

Write a method to return all subsets of a set.

CTCI 9.4-1.java

//recursive
public static ArrayList<ArrayList<Character>> findSubsets(char[] input){
    ArrayList<ArrayList<Character>> listOfSubsets= new ArrayList<ArrayList<Character>>();
    listOfSubsets.add(new ArrayList<Character>());
    findSubsets(input, 0, listOfSubsets);
    return listOfSubsets;
}
public static void findSubsets(char[] input, int index, ArrayList<ArrayList<Character>> listOfSubsets){
    if(index >= input.length) return;
    ArrayList<ArrayList<Character>> newListOfSubsets = new ArrayList<ArrayList<Character>>();
    for(ArrayList<Character> subset : listOfSubsets){
        ArrayList<Character> newSubset = new ArrayList<Character>();
        newSubset.addAll(subset);
        newSubset.add(input[index]);
        newListOfSubsets.add(newSubset);
    }
    listOfSubsets.addAll(newListOfSubsets);
    findSubsets(input, index + 1, listOfSubsets);
}

CTCI 9.4-2.java

//binary
public static ArrayList<ArrayList<Character>> findSubsets(char[] input){
    ArrayList<ArrayList<Character>> listOfsubsets = new ArrayList<ArrayList<Character>>();
    int num = 1 << input.length;
    for(int i = 0; i < num; i++) listOfsubsets.add(getSubsetFromBinary(i, input));
    return listOfsubsets;
}
public static ArrayList<Character> getSubsetFromBinary(int i, char[] input){
    ArrayList<Character> thisSubset = new ArrayList<Character>();
    for(int index = 0; i != 0; i >>= 1, index++) if((i & 1) != 0) thisSubset.add(input[index]);
    return thisSubset;
}