題目

輸入一個字符串，打印出該字符串中字符的所有排列。
例如，輸入字符串a(chǎn)bc，則打印出由字符a、b、c所能排列出來的所有字符串a(chǎn)bc、acb、bac、bca、cab和cba。

解題思路

1. 求所有可能出現(xiàn)在第一個位置的字符，即把第一個字符和后面所有的字符交換
2. 固定第一個字符，求后面所有字符的排列(把后面的所有字符分成兩部分:后面字符的第一個字符以及這個字符之后的所有字符，然后把第一個字符逐一和它后面的字符交換)。

代碼

• 細(xì)節(jié)
  指針pstr指向整個字符串的第一個字符，指針pBegin指向當(dāng)前我們執(zhí)行排列操作的字符串的第一個字符。每一次遞歸的時候，從pBegin向后掃描每一個字符(指針pch指向的字符)。交換pBegin和pch指向的字符后，如果pbegin沒有走到末尾，會一直交換到末尾然后輸出此時的排序字符串，再返回。
  這個代碼不好理解，我把每一步的輸出放在這里。
  
  image.png
  
  第一個swap是求所有可能出現(xiàn)在第一個位置的字符。然后固定第一個字符，遞歸后面的字符并排序。第二個swap是把字符恢復(fù)原狀(我個人理解，歡迎說出你的理解)。接著找第二個固定的字符，然后遞歸后面的字符并排序。

class Solution{
    public:
        void swap(char *a,char *b)
        {
            char temp = *a;
            *a        = *b;
            *b        = temp;
        }
        void percore(char *pstr,char *pbegin)
        {
            if(*pbegin == '\0')
            {
                cout <<pstr << endl;
            }
            else
            {
                for(char *pch=pbegin;*pch!='\0';pch++)
                {
                    //cout << "交換前:" << *pch << " " << *pbegin ;
                    swap(pch,pbegin);
                    //cout << " 交換后:" << *pch << " " << *pbegin << endl;;
                    percore(pstr,pbegin+1);
                    //cout << "遞歸后:" ; 
                    //cout << "交換前:" << *pch << " " << *pbegin ;
                    swap(pch,pbegin);
                    //cout << " 交換后:" << *pch << " " << *pbegin << endl;;
                }
            }
        }
        void Permutation(char str[])
        {
            percore(str,str);
        }
};

完整代碼見Github