a bit on backtracking

If there is one thing that computer can do very well, it is backtracking. Backtracking is one of the most fundamental problem solving paradigm: given a problem, try all possible input to come up with the solutions. This is what we did when girlfriends suddenly get angry at us, we need to generate all possibilities very quickly until a solution is found. Implementation of backtracking algorithms usually makes use of recursion, sometimes referred to as 'recursive algorithm'. The advantages of backtracking is a solution set can be produced with minimum knowledge and understanding about the problem itself. Sometimes, the only way to solve a given problem is through backtracking. Yet, this method grows very quickly in terms of complexity, hence can only be applied on problems that work on small set of input.

There are 2 basic type of backtracking algorithm that will be presented here, namely finding subsets and generating permutations. A set H is called a subset of S if and only if H contains only elements in S. A permutation is defined as a rearrangement of elements in an ordered set.

For example, given a set S = {1,2,5}, we have exactly 8 subsets of S: {1,2,5}, {1,2}, {1,5}, {2,5}, {1}, {2}, {5}, and {}.

Given an ordered set P = {1,3,4}, there are exactly 6 permutations using all elements in P: {1,3,4}, {1,4,3}, {3,1,4}, {3,4,1}, {4,1,3}, {4,3,1}.

Backtracking algorithms build valid inputs by adding a new element one by one to an existing set until a solution is found. A simple implementation of backtracking algorithm to find subsets is described as follows:

//a[N] initial set, S[N] is describes the subset of a[N]

//S[i] is 1 if a[i] is in the subset, and 0 otherwise

void backtrack_subset(int a[N],bool S[N],int k){

  if(k==N){

    printf("{ ");

    for(int i=0;i<N;++i){

      if(S[i])printf("%d ",a[i]);

    }
    printf("}\n");

    return;

  }

  bool c[2]={true,false}; //new elements

  for(int i=0;i<2;++i){

    S[k]=c[i];

    backtrack_subset(a,S,k+1);

  }

}

The function starts with a call backtrack_subset(a,S,0)and terminates when k equals to N, for which a valid subset of a[N] has been constructed. The complexity of this algorithm grows exponentially, as each calls to backtrack_subset will lead to 2 calls of backtrack_subset. My 5-year old Mac withstood (with much struggling) up to N=20.

Next we have an implementation of backtracking on permutations:

void backtrack_perm(int a[N],int P[N],int k){

  if(k==N){

    printf("{ ");

    for(int i=0;i<N;++i){printf("%d ",a[P[i]]);}

    printf("}\n");

    return;

  }

  bool ins[N]; //if i is inside P[i], ins[i] = 1, otherwise 0

  for(int i=0;i<N;++i)ins[i]=false;

  for(int i=0;i<k;++i)ins[P[i]]=true;

  int np=0;int c[N];   //c stores possible next element

  for(int i=0;i<N;++i){

    if(ins[i]==false){

      c[np]=i;

      ++np;

    }

  }

  for(int i=0;i<np;++i){

    P[k]=c[i];

    backtrack_perm(a,P,k+1,cnt);

  }

}

This algorithm has exactly the same idea with the previous one, in which the significant difference is the way it stores the information about whether an element a[i] is already inside the permutation. This algorithm have O(N!) complexity, hence can only be useful for N up to 10. Each call of backtrack_perm leads to another np calls to backtrack_perm where np is the number of available choices of new elements that can be added. My Mac surrendered on N=11 in which I had to hard reboot the poor machine. This idea of recursive calls to next available elements is also used in many other advanced algorithm such as graph traversal algorithms. :)