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("%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
       }
   }
}

Answer 1

“回溯”将字符串调换回其原始状态，这对于算法的正确运行至关重要。

您不希望您的函数弄乱您的输入字符串，对吗？