首先我們區(qū)分一下排列和組合：

• 輸入一個字符串，得到這個字符串的所有組合（不是排列）：
  比如輸入abc，得到a,ab,ac,b,bc,abc,c
• 排列：a(bc),a(cb),b(ac),b(ca),c(ab),c(ba)

組合

把問題簡化為長度為n的字符串中求m個字符串的組合。
我可以從第一個字符開始，有兩種情況：
1，含有這個字符，然后求剩下m-1個字符串的組合；
2，不含有這個字符，然后求剩下m個字符串的組合；
a+a(fun(bc))+fun(bc)
fun(bc):
b+bfun(c)+fun(c)
也就是：
b,bc,c
so:
a,a(b,bc,c),(b,bc,c)

和很多字符串的題目一樣，我們使用遞歸的方法：
首先是驅(qū)動函數(shù)：

#include <iostream>
#include <vector>

void combination(char* str, int number, std::vector<char>& vec);

void combinate(char* str)
{
    if (!str)
        return;
    size_t len = strlen(str);

    std::vector<char> str_vec;

    for (int i = 1; i <= len; i++)
    {
        combination(str, i, str_vec);
    }
}

首先我們檢測輸入是否合法，然后我們從第一個字符串開始，得到關(guān)于當(dāng)前這個字符和后面字符串（看成一個整體）的序列，而后面所有字符的情況只需要遞歸的調(diào)用就好了

void combination(char* str, int number, std::vector<char>& vec)
{
    if (number == 0)
    {
        auto beg = vec.begin();
        for (beg; beg!=vec.end(); beg++)
            std::cout << *beg;
        std::cout << std::endl;
    }
    if (*str != '\n')
        return;

    vec.push_back(*str);
    combination(str+1, number - 1, vec);

    vec.pop_back();
    combination(str + 1, number, vec);

}

我們的參數(shù)列表包括字符串的指針，當(dāng)前字符的位置number,還有存儲在vector里面的字符（等待打?。?。

這個函數(shù)就是按照前面的思路寫的：

1，含有這個字符，然后求剩下m-1個字符串的組合；
2，不含有這個字符，然后求剩下m個字符串的組合；

情況1對應(yīng)：
vec.push_back(*str); combination(str+1, number - 1, vec);
情況2：
vec.pop_back(); combination(str + 1, number, vec);
先把當(dāng)前字符刪除，然后打印

最后，說實(shí)話，看了這么多遞歸，感覺真的寫得好，，可是我就是不會哈哈哈。。

排列

• 排列：a(bc),a(cb),b(ac),b(ca),c(ab),c(ba)

這一部分在8皇后問題里面已經(jīng)用到過這個方法了；
思路就像上面舉例子寫的一樣，通過交換位置來達(dá)到目的。
我們分別把每個字符放到最開始的位置，而剩余的字符使用遞歸的方法來做同樣的事情。

核心部分：
//偽代碼 swap(*pch,*pbegin); permutation(pbegin+1); swap(*pch,*pbegin);
這個要遞歸兩遍吧，實(shí)際情況很復(fù)雜的。

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;
            }
        }
}

文章參考何海濤大神文章