////////////////////////////////////////////////////////////////////////////////
//  << j571b.java >>
//
//  スレッド(7):バックトラックアルゴリズムのスレッド化
//
// ●問題
//
//  集合{1,2,...,n}上のすべての部分集合b[1]b[2]...b[n]を生成する。
//    ただし、要素iが部分集合に含まれるときb[i]=1,含まれないときb[i]=0とする。
//
// ●解法
//
//  新たなクラスを生成し、その中で再帰的メソッドを使う。
//
////////////////////////////////////////////////////////////////////////////////

class C {
  int b[]; // 部分集合を表す配列。 
  int count = 0; // 生成された部分集合の個数。
  C(int n) { // コンストラクタ。
    b = new int[n+1];
  }
  // 集合{k,...,n}上のすべての部分集合b[k]...b[n]を生成する。
  void gen(int k, int n) {
    if( k > n ) {
      count++; System.out.print(count + ": ");
      for( int i=1; i<=n; i++ ) { System.out.print(b[i]); }
      System.out.println();
    } else {
      b[k] = 0; gen(k+1,n);
      b[k] = 1; gen(k+1,n);
    }  
  }
}

class j571b {
  public static void main(String args[]) {

    int n = Integer.parseInt(args[0]); // args[0]は集合のサイズnを表す。

    System.out.println("集合のサイズ:" + n);

    C obj = new C(n);

    obj.gen(1,n);

  }

}
実行結果
% javac j571b.java
% java j571b 4
集合のサイズ:4
1: 0000
2: 0001
3: 0010
4: 0011
5: 0100
6: 0101
7: 0110
8: 0111
9: 1000
10: 1001
11: 1010
12: 1011
13: 1100
14: 1101
15: 1110
16: 1111