import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Objects;
import java.util.Set;
import java.util.TreeSet;

public class PowerSet {

    private class listComparator implements Comparator<List<Integer>> {

        @Override
        public int compare(List<Integer> o1, List<Integer> o2) {
            if (o1.equals(o2)) {
                return 0;
            }
            if (o1.size() != o2.size()) {
                return ((new Integer(o1.size()).compareTo(o2.size())));
            } else {
                for (int i = 0; i < o1.size(); i++) {
                    if (!Objects.equals(o1.get(i), o2.get(i))) {
                        return o1.get(i).compareTo(o2.get(i));
                    }
                }
            }
            throw (new RuntimeException("Logic error comparing " + o1 + " and "
                    + o2));
        }
    }

    final private List<Integer> data;
    final private Set<List<Integer>> powerSet;

    final static private String USAGE = "Please specify set size.";

    public PowerSet() {
        data = new ArrayList<>();
        powerSet = new TreeSet<>(new listComparator());
    }

    public PowerSet(int length) {
        this();
        int i = 0;
        while (i < length) {
            data.add(i);
            i++;
        }
    }

    public Set getPowerSet() {
        return this.powerSet;
    }

    public void run() {
        final int n = data.size(); // If the set contains n elements, then
        final int e = 1 << n;      // the power set will contain 2^n elements.

        // Loop through each power set element. i is a number representing
        // a unique combination of set elements between [0,2^n-1]
        for (int i = 0; i < e; i++) {
            List<Integer> subset = new ArrayList<>();

            // The binary digits of i indicate the presence or absence of
            // set elements relative to the original data in this subset.
            // 1 in the respective element's position means it is present.
            // 0 means that it is not. Elements from the original set are
            // only added to the subset if the 1 is turned on.
            for (int j = 0; j < n; j++) {
                if (((1 << j) & i) > 0) {
                    subset.add(data.get(j));
                }
            }

            // Thanks to the use of a TreeSet and custom Comparator class,
            // these sets will be automatically sorted.
            powerSet.add(subset);
        }
    }

    public static void main(String[] args) {
        int i = 0;
        try {
            if (args.length > 0) {
                i = Integer.parseInt(args[0]);
            } else {
                System.out.println(USAGE);
                System.exit(0);
            }
        } catch (NumberFormatException e) {
            System.out.println(e);
            System.out.println(USAGE);
            System.exit(0);
        }
        PowerSet ps = new PowerSet(i);
        ps.run();
        System.out.println(ps.getPowerSet());
    }
}