We may represent a subset of n elements by the one-dimensional array x[1:n], where x[j] is one if element j is included in the subset and x[j] is zero if element j is not included in the subset.
To output the subsets recursively, we define a method subsets(int i) which outputs all x[1:n] with preset values for x[1:i-1] and x[i:n] taking on all possible 0 and 1 values. The invocation subsets(1) will output all subsets.
1 /** generate all subsets of n elements */ 2 3 package applications; 4 5 public class AllSubsets 6 { 7 // class data member 8 static int [] x; // subset vector 9 10 /** define array x and invoke private method subsets */ 11 public static void allSubsets(int n) 12 { 13 x = new int [n + 1]; 14 // output all subsets of x[1:n] 15 subsets(1); 16 } 17 18 /** output x[1:i-1] followed by all subsets of x[i:x.length-1] */ 19 private static void subsets(int i) 20 { 21 if (i == x.length - 1) 22 {// x[x.length - 1] can be 0 or 1 23 // output subset without last element 24 x[x.length - 1] = 0; 25 for (int j = 1; j <= x.length - 1; j++) 26 System.out.print(x[j] + " "); 27 System.out.println(); 28 29 // output subset with last element 30 x[x.length - 1] = 1; 31 for (int j = 1; j <= x.length - 1; j++) 32 System.out.print(x[j] + " "); 33 System.out.println(); 34 return; 35 } 36 37 // leave element i out 38 x[i] = 0; 39 // generate all subsets with i excluded 40 subsets(i + 1); 41 42 // put element i into subset 43 x[i] = 1; 44 // generate all subsets with i included 45 subsets(i + 1); 46 } 47 48 /** test program */ 49 public static void main(String [] args) 50 { 51 allSubsets(4); 52 } 53 }
