## Tuesday, October 9, 2012

### Constructing All Subsets

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();
}
}
```