Constructing All Subsets

This article is pretty similar with the previous one, which using backtracking tech to generate all of the subsets of the given set.

Result of the test case:

{  }
{  a }
{  c }
{  c a }
{  b }
{  b a }
{  b c }
{  b c a }
{  d }
{  d a }
{  d c }
{  d c a }
{  d b }
{  d b a }
{  d b c }
{  d b c a }
*************************
{  }
{  d }
{  c }
{  c d }
{  b }
{  b d }
{  b c }
{  b c d }
{  a }
{  a d }
{  a c }
{  a c d }
{  a b }
{  a b d }
{  a b c }
{  a b c d }

/**
 * @author antonio081014
 * @time: Oct 9, 2012, 5:44:20 PM
 */
public class SubSets {

 /**
  * @param args
  */
 public static void main(String[] args) {
  SubSets main = new SubSets();
  String[] s = { "d", "b", "c", "a" };
  main.subset(s);
  System.out.println("*************************");
  main.subset(new String[] { "a", "b", "c", "d" });
 }

 public void subset(String[] s) {
  int[] a = new int[s.length];
  backtrack(a, 0, s);
 }

 /*
  * The first k-1 indices is stored in a, here we need to choose the kth
  * element;
  */
 public void backtrack(int[] a, int k, String[] s) {
  // if we reach the end;
  if (is_a_solution(a, k, s)) {
   // print(a, k);
   process_solution(a, k, s);
   return;
  }

  int[] candidates = construct_candidates(a, k, s);
  // k = k + 1;
  for (int i = 0; i < candidates.length; i++) {
   a[k] = candidates[i];
   // make_move(a,k,s);
   // int[] tmp = Arrays.copyOf(a, s.length);
   backtrack(a, k + 1, s);
   // unmake_move(a,k,s);
   // a = Arrays.copyOf(tmp, s.length);

   // check if finished;
  }
 }

 public int[] construct_candidates(int[] a, int k, String[] s) {
  // Only two possibility exists;
  int[] ret = { 0, 1 };
  return ret;
 }

 /*
  * Process the permutation, which is the array of the indices;
  */
 public void process_solution(int[] a, int k, String[] s) {
  System.out.print("{ ");
  for (int i = 0; i < s.length; i++) {
   if (a[i] == 1) {
    System.out.print(" ");
    System.out.print(s[i]);
   }
  }
  System.out.println(" }");
 }

 public boolean is_a_solution(int[] a, int k, String[] s) {
  // Reach the limit, which there is no element here;
  int n = s.length;
  return k == n;
 }

 // Check the permutation indices;
 public void print(int[] a, int k) {
  for (int i = 0; i < k; i++, System.out.print(" "))
   System.out.print(a[i]);
  System.out.println();
 }
}