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");

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. :)