字元串的排列

題目

　　輸入一個字元串，列印出該字元串中字元的所有排列。例如輸入字元串abc，則列印出由字元a、b、c所能排列出來的所有字元串abc、acb、bac、bca、cab和cba。

思路

排列

可分為兩步

1. 求所有可能出現在第一個位置的字元，就是把第一個字元和後面的所有字元交換
2. 固定第一個字元，求後面所有的字元排列

　　　　1.所有可能出現在 後面第一個字元的字元

　　　　2.這個字元後面的全排列

可以遞歸求解...

組合

　　n個字元串求長度為m組合的時候，可以可以把字元串分為兩部分，第一個字元即第一個字元後面的所有字元

• 　　如果組合包含第一個字元，則在餘下的字元串裡求m-1個字元
• 　　如果組合不包含第一個字元，則下一步在餘下的n-1個子字元裡選取m個字元。

　　也就是說們可以轉化為如下的兩個子問題。

1. 　　求n-1個字元串中長度為m-1的組合
2. 　　求n-1個字元串中長度為m的組合

class Solution {
private:
    void dfs(string &s, int index, vector<string> &res) {
        if (index == s.size()) {
            res.push_back(s);
            return;
        }

        for (int i = index; i < s.size(); ++i) {
            bool falg = false;
            for (int j = index; j < i; ++j) {
                if (s[i] == s[j]) {
                    falg = true;
                }
            }
            if (falg == false) {
                swap(s[i], s[index]);
                dfs(s, index + 1, res);
                swap(s[index], s[i]);
            }            
        }
        return ;
    }
public:
    vector<string> permutation(string s) {
        if (s.empty()) {
            return {};
        }

        vector<string> res;
        int index = 0;
        dfs(s, index, res);
        sort(res.begin(), res.end());
        return res;
    }
};      

　　關于排列組合算法的詳解，也可以參考： https://www.cnblogs.com/tianzeng/p/10055489.html

拓展