// PowerSets.java
// Computes all the possible subsets of the set { 0, 1, 2, ..., n-1 }.
// Note that the set of all possible subsets is called the "power set".

import java.util.*;

public class PowerSets {
  public static void main(String[] args) {
    test1();
    test2();
  }

  public static void test1() {
    PowerSet ps = new PowerSet(4);
    while (ps.hasNext()) {
      int[] a = ps.next();
      System.out.println(Arrays.toString(a));
    }
  }
  
  public static void test2() {
    Scanner scanner = new Scanner(System.in);
    System.out.print("Enter n: ");
    int n = scanner.nextInt();
    PowerSet ps = new PowerSet(n);
    System.out.println("Here are all the possible subsets " +
                       "among " + n + " objects:");
    int counter = 0;
    while (ps.hasNext()) {
      int[] next = ps.next();
      System.out.println(Arrays.toString(next));
      counter++;
    }
    System.out.println("total = " + counter);
    System.out.println("Note that this equals 2^" + n + " = " + (int)(Math.pow(2,n)));
  }
}

//////////////////////////////////////
// PowerSet
//
// You do not need to write the code below here.
// You just need to be able to USE it.
//////////////////////////////////////

class PowerSet {
  private int n;
  private int index = 0;
  private boolean hasNext = true;
    
  public PowerSet(int n) {
    this.n = n;
  }

  public boolean hasNext() { return hasNext; }

  public int[] next() {
    if (!hasNext) return null;
    // the 1 bits of "index" indicate which numbers to include in this subset
    int bits, j=0, k=0;
    for (bits=index; bits>0; bits/=2) k += bits%2; // k = # of bits set to 1
    int[] result = new int[k];
    bits = index;
    for (int i=0; i<n; i++) {
      if (bits % 2 == 1) result[j++] = i;
      bits /= 2;
    }
    if (k == n) hasNext = false; // last one!
    index++;
    return result;
  }
}