Recursion has always fascinated me for its simplicity. Whenever I come across a new recursive equation I had never known I feel happy about knowing it. But then there is a trade of with this simplicity for they say that in general recursive solutions are not as efficient as their iterative versions. Being a computer science geek and attached to algorithm programming, I am obsessed about efficiency of the code I write but recursion for its simplicity always allows me that exception. A road less traveled for me has been backtracking for backtracking involves trying all possibilities and it sounds awful in terms of complexities to say the least when you hear that first. But sometimes it is the only solution available or at least I see some classic problems like 8-queens problem which people solve using backtracking. It is for this reason that I thought it would be good to cover a post on backtracking to throw in some much deserved respect to this genre of algorithms. Lets try and learn backtracking approach to algorithms. Lets go through some simple problems to understand the idea. The first code we will write here is to generate all strings of n bits. For simplicity, we assume that we have a global array 'ar' available. Here is the code:
{
if(n<1) printf("%s\n", ar);
else{
for(int j=0;j<k;j++) //iterate over all k elements.
{
ar[n-1]='0'+j; //fix the (n)th position
generate_all(n-1,k); //generate all combinations for other n-1 positions.
}
}
}
[/sourcecode]
The output of this code is as follows:
000 100 200 300 010 110 210 310 020 120 220 320 030 130 230 330 001 101 201 301 011 111 211 311 021 121 221 321 031 131 231 331 002 102 202 302 012 112 212 312 022 122 222 322 032 132 232 332 003 103 203 303 013 113 213 313 023 123 223 323 033 133 233 333
This code is also exponential in nature- O(k^n). Here k=4 and n=3, so we have 64 strings in the output. Lets now add just a little more logic to that. We now write a code to print all permutations of a given string. The input string can be anything as opposed to first k characters starting with '0' in the earlier example.
[sourcecode language="cpp"]
#include
#include
#include
using namespace std;
void generate_all(int depth, char* permutation, int *used, char *original)
{
int length=strlen(original);
if(depth==length){ //base case
permutation[depth]='\0'; //so that we have an end marker for the string
printf("%s\n", permutation);
}
else{
for(int i=0;i<length;i++){
if(!used[i]){
used[i]=1; //Mark this position in "permutation" string used
permutation[depth]=original[i]; //fix the (i)th position
generate_all(depth+1, permutation, used, original); //generate all permutations for remaining (not marked used yet)positions
used[i]=0; //Prepare to backtrack
}
}
}
}
int main()
{
int used[]={0,0,0};
char * p;
char original[]="abc";
generate_all(0, p, used,original);
return 0;
}
[/sourcecode]
The output of the above code is:
abc acb bac bca cab cba
If we instead make our input string: "aaa", we get the output:
aaa aaa aaa aaa aaa aaa
I found the same question (last one) on geeksforgeeks but they solve it differently which is not very intuitive to me. To print only the unique strings in output, you can follow this code. This post is a primer and hence let us stop here. Try not to learn the exact questions and their solution but the way recursion unfolds and the way it backtracks again to look at the other parts of solution. Since we stop here with pretty basic stuff, let me make a promise to cover more backtracking codes in the coming posts. In the meantime if you are interested, have a look at the classic 8-queens problem and how backtracking is used to solve it.
void generate_all(int n)
{
if(n<1) printf("%s\n", ar);
else{
ar[n-1]='0'; //fix (n)th bit as '0'
generate_all(n-1); //generate all combinations for other n-1 positions.
ar[n-1]='1'; //fix (n)th bit as '1'
generate_all(n-1); //generate all combinations for other n-1 positions.
}
}
The output of this code is:
000 100 010 110 001 101 011 111
The code is exponential in complexity- O(2^n). Here n=3, so we have 8 strings in the output. Lets now generalize this code to print k-ary strings.
void generate_all(int n, int k){
if(n<1) printf("%s\n", ar);
else{
for(int j=0;j<k;j++) //iterate over all k elements.
{
ar[n-1]='0'+j; //fix the (n)th position
generate_all(n-1,k); //generate all combinations for other n-1 positions.
}
}
}
[/sourcecode]
The output of this code is as follows:
000 100 200 300 010 110 210 310 020 120 220 320 030 130 230 330 001 101 201 301 011 111 211 311 021 121 221 321 031 131 231 331 002 102 202 302 012 112 212 312 022 122 222 322 032 132 232 332 003 103 203 303 013 113 213 313 023 123 223 323 033 133 233 333
This code is also exponential in nature- O(k^n). Here k=4 and n=3, so we have 64 strings in the output. Lets now add just a little more logic to that. We now write a code to print all permutations of a given string. The input string can be anything as opposed to first k characters starting with '0' in the earlier example.
[sourcecode language="cpp"]
#include
#include
#include
using namespace std;
void generate_all(int depth, char* permutation, int *used, char *original)
{
int length=strlen(original);
if(depth==length){ //base case
permutation[depth]='\0'; //so that we have an end marker for the string
printf("%s\n", permutation);
}
else{
for(int i=0;i<length;i++){
if(!used[i]){
used[i]=1; //Mark this position in "permutation" string used
permutation[depth]=original[i]; //fix the (i)th position
generate_all(depth+1, permutation, used, original); //generate all permutations for remaining (not marked used yet)positions
used[i]=0; //Prepare to backtrack
}
}
}
}
int main()
{
int used[]={0,0,0};
char * p;
char original[]="abc";
generate_all(0, p, used,original);
return 0;
}
[/sourcecode]
The output of the above code is:
abc acb bac bca cab cba
If we instead make our input string: "aaa", we get the output:
aaa aaa aaa aaa aaa aaa
I found the same question (last one) on geeksforgeeks but they solve it differently which is not very intuitive to me. To print only the unique strings in output, you can follow this code. This post is a primer and hence let us stop here. Try not to learn the exact questions and their solution but the way recursion unfolds and the way it backtracks again to look at the other parts of solution. Since we stop here with pretty basic stuff, let me make a promise to cover more backtracking codes in the coming posts. In the meantime if you are interested, have a look at the classic 8-queens problem and how backtracking is used to solve it.
