String permutation - How does this backtracking recursion work?

Question

This function basically prints all possible permutations of a string by swapping a character with all its other characters. I understand the first two calls to swap and permute. But why is swap called for the second time? I cannot understand this piece of code. Can someone please explain me how this works?

/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
void permute(char *a, int l, int r)
{
   int i;
   if (l == r)
     printf("%s\n", a);
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));
          permute(a, l+1, r);
          swap((a+l), (a+i)); //backtrack
       }
   }
}

Bathsheba Bathsheba · Accepted Answer · 2015-08-04T13:47:25

The "backtrack" swaps the string back to its original state, which is vital for the correct running of the algorithm.

You wouldn't want your function to mess up your input string, would you?

String permutation - How does this backtracking recursion work?

1 Answers