9.5 编写一个方法，确定某字符串的所有排列组合。
类似leetcode：Permutations
解法：
跟许多递归问题一样，简单构造法非常管用。假设有个字符串S，以字符序列a1a2a...an表示。
终止条件：n=1
S=a1，只有一种排列组合，即字符串a1
情况：n=2
S=a1a2 有两种排列组合a1a2和a2a1
情况：n
对于一般情况下，我们只需重复这个步骤。即已经求得f(n-1)的解，接着只要将an插入到这些字符串的任意位置。
c++代码实现：
#include<iostream>
#include<vector>
#include<string>
using namespace std; vector<string> getPerms(string str)
{
if(str.empty())
return vector<string>();
int n=str.length();
vector<string> res;
res.push_back(string(""));
vector<string> r;
int i,j;
for(i=;i<n;i++)
{
char c=str[i];
r=res;
res.clear();
for(j=;j<r.size();j++)
{
string tmp=r[j];
int index=;
while(tmp.begin()+index!=tmp.end())
{
tmp.insert(tmp.begin()+index,c);
res.push_back(tmp);
tmp=r[j];
index++;
}
tmp.push_back(c);
res.push_back(tmp);
}
}
return res;
} int main()
{
string str="abc";
vector<string> res=getPerms(str);
for(auto s:res)
cout<<s<<endl;
}