在做字符串相关问题时，有时需要遍历字符串所有可能的排列。比如 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;
}
