Question9_4.java

import java.util.LinkedList;

/**
 * Write a method to return all subsets of a set.
 * 
 * Time  Complexity: O(2^n)
 * Space Complexity: O(2^n)
 */

public class Question9_4 {
    public LinkedList<LinkedList<Integer>> subsets(int[] set) {
        LinkedList<LinkedList<Integer>> subsets = new LinkedList<LinkedList<Integer>>();
        if (set != null && set.length != 0) {
            subsets.add(new LinkedList<Integer>());
            for (int i = 0; i < set.length; ++i) {
                int size = subsets.size();
                for (int j = 0; j < size; ++j) {
                    LinkedList<Integer> subset = new LinkedList<Integer>(subsets.get(j));
                    subset.add(set[i]);
                    subsets.add(subset);
                }
            }
        }
        return subsets;
    }
    
    
    public static void main(String[] args) {
        Question9_4 question9_4 = new Question9_4();
        LinkedList<LinkedList<Integer>> subsets = question9_4.subsets(new int[] {0, 1, 2});
        for (int i = 0; i < subsets.size(); ++i) {
            System.out.println(subsets.get(i).toString());
        }
    }
}