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

class j571a {
  static int n; // 集合のサイズ。
  static int count = 0; // 生成された部分集合の個数。
  static int b[]; // 部分集合を表す配列。 

  // 集合{k,...,n}上のすべての部分集合b[k]...b[n]を生成する。
  static 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]=0とし、集合{k+1,...,n}上のすべての
                            // 部分集合b[k+1]...b[n]を生成する。
      b[k] = 1; gen(k+1,n); // b[k]=1とし、集合{k+1,...,n}上のすべての
                            // 部分集合b[k+1]...b[n]を生成する。
    }  
  }

  public static void main(String args[]) {

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

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

    b = new int[n+1];

    gen(1,n); // 集合{1,...,n}上のすべての部分集合b[1]...b[n]を生成する。
    
  }

}
実行結果
% javac j571a.java
% java j571a 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