在做字符串相关问题时，有时需要遍历字符串所有可能的排列。比如 abc, 可能有abc, acb, bac, bca....等情况。本文通过分治的方法，求得了输入字符串的所有排列集合，下面对算法进行分析。
注意：从理论上分析，这是一个排列组合问题，所以复杂度不会在多项式时间，应该是O(N!), 所以当输入字符串超过7位时，使用这个算法将花费很长时间，请退一步反思求解思路是否有问题。

思路><分治法

找出子问题

一个字符串变量假如是str，既然是str的全排列，那么str的每一个字符都可以打头。那么子问题可以是：

求某一个字符打头的字符串的全排列。

分别求str每个字符打头的排列，然后把他们并起来，结果就是str的所有字符排列的可能性。

比如：string str = "abc"; 那么子问题分别是:

{以a开头的排列集合} ∪ {以b开头的集合} ∪ {以c开头的集合}.

递归求解子问题

分两种情况：

• 字符串长度为1，那么排列为自身，这是递归的出口。
• 字符串长度大于1，循环考虑str中每一个字符开头的情况。每一次循环，假如开头为某一字符，后面得追加上剩余长度为size -1的字符串的各种排列【调用函数本身】即可。

例如：abc, 需要分别考虑将a，b , c 打头的情况，对于以b打头：

• b开头 追加上剩余部分：ac字符串的全排列，最终得到 bac, bca。
• 而ac字符串的全排列是通过递归调用函数本身得到的，即考虑ac中以a打头和以c打头的并集。

不重复

我这里打头字符是通过循环和swap函数结合使用实现的。

当我们swap的时候，与开头字母swap的字符可能与开头字符相同，这种情况下即使swap了，剩余部分的计算结果一定与前面重复。同理，当我们已经考虑过某一字符打头的情况时，就不需要在后面的遍历中，再次swap它到前面来。

方法：维护一个记忆表，保存已经考虑过的开头字符，每次swap前，都检查是否计算过.

代码以及注释

// 需要包含，<vector>,<string>,<iostream>等STL标准库。
vector<string> permutation(string str) {
    if (str.size() == 1)
        return { str };
    else {
        vector<string> re;  //存储各种排列
        
        //原字母开头的
        //递归调用，返回字串的各种排列
        vector<string> sub_pt = permutation(str.substr(1)); 
        for (int i = 0; i < sub_pt.size(); ++i) {
            //原首字母与剩余子串各种排列的组合，加入返回列表
            re.push_back(str.at(0) + sub_pt.at(i));
        }
        //通过交换使得身后其它字母开头
        vector<char> save;  //记录不必再交换的
        save.push_back(str.at(0));  //与首字母相同自然不用交换
        for (int i = 1; i < str.size(); ++i) {
            if (find(save.begin(), save.end(), str.at(i)) != save.end())
                continue; //如果该字符已经考虑过了，则跳过
            string temp = str;
            save.push_back(temp.at(i));//将该字符加入记忆表
            swap(temp.at(0), temp.at(i));
            vector<string> sub_pt = permutation(temp.substr(1));//递归调用
            for (int i = 0; i < sub_pt.size(); ++i) {
                //新首字母与剩余子串各种排列的组合，加入返回列表
                re.push_back(temp.at(0) + sub_pt.at(i));
            }
        }
        return re;
    }