C语言 字符串排列-回溯递归是如何工作的

Question

这个函数基本上通过将一个字符与所有其他字符交换来打印字符串的所有可能排列。我理解前两次互换和排列的调用。但是为什么swap会被第二次调用呢?我看不懂这段代码。有人能告诉我这是怎么回事吗?

/* 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("%sn", a);
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));
          permute(a, l+1, r);
          swap((a+l), (a+i)); //backtrack
       }
   }
}

Answer 1

"backtrack"将字符串交换回原始状态，这对于算法的正确运行至关重要。

你不希望你的函数弄乱你的输入字符串，你会吗?