分析：這是一道很好的考查對遞歸理解的編程題，因此在過去一年中頻繁出現(xiàn)在各大公司的面試、筆試題中。

我們以三個字符abc為例來分析一下求字符串排列的過程。首先我們固定第一個字符a，求后面兩個字符bc的排列。當兩個字符bc的排列求好之后，我們把第一個字符a和后面的b交換，得到bac，接著我們固定第一個字符b，求后面兩個字符ac的排列?，F(xiàn)在是把c放到第一位置的時候了。記住前面我們已經(jīng)把原先的第一個字符a和后面的b做了交換，為了保證這次c仍然是和原先處在第一位置的a交換，我們在拿c和第一個字符交換之前，先要把b和a交換回來。在交換b和a之后，再拿c和處在第一位置的a進行交換，得到cba。我們再次固定第一個字符c，求后面兩個字符b、a的排列。

既然我們已經(jīng)知道怎么求三個字符的排列，那么固定第一個字符之后求后面兩個字符的排列，就是典型的遞歸思路了。

基于前面的分析，我們可以得到如下的參考代碼：

void Permutation(char* pStr, char* pBegin);

/////////////////////////////////////////////////////////////////////////
// Get the permutation of a string,
// for example, input string abc, its permutation is
// abc acb bac bca cba cab
/////////////////////////////////////////////////////////////////////////
void Permutation(char* pStr)
{
      Permutation(pStr, pStr);
}

/////////////////////////////////////////////////////////////////////////
// Print the permutation of a string,
// Input: pStr   - input string
//        pBegin - points to the begin char of string
//                 which we want to permutate in this recursion
/////////////////////////////////////////////////////////////////////////
void Permutation(char* pStr, char* pBegin)
{
      if(!pStr || !pBegin)
            return;

      // if pBegin points to the end of string,
      // this round of permutation is finished, 
      // print the permuted string
      if(*pBegin == '/0')
      {
            printf("%s/n", pStr);
      }
      // otherwise, permute string
      else
      {
            for(char* pCh = pBegin; *pCh != '/0'; ++ pCh)
            {
                  // swap pCh and pBegin
                  char temp = *pCh;
                  *pCh = *pBegin;
                  *pBegin = temp;

                  Permutation(pStr, pBegin + 1);

                  // restore pCh and pBegin
                  temp = *pCh;
                  *pCh = *pBegin;
                  *pBegin = temp;
            }
      }
}

擴展1：如果不是求字符的所有排列，而是求字符的所有組合，應(yīng)該怎么辦呢？當輸入的字符串中含有相同的字符串時，相同的字符交換位置是不同的排列，但是同一個組合。舉個例子，如果輸入aaa，那么它的排列是6個aaa，但對應(yīng)的組合只有一個。

擴展2：輸入一個含有8個數(shù)字的數(shù)組，判斷有沒有可能把這8個數(shù)字分別放到正方體的8個頂點上，使得正方體上三組相對的面上的4個頂點的和相等。