问题描述：
给你一个字符串，求出字符串的所有排列
例如：“abc”
输出：“abc”,“acb”,“bac”,“bca”,“cab”,“cba”
思路求解：
我们可以根据原字符串，进行交换即可
例如：我们的0位置与0位置交换，代表我们本次字符不交换
我们0和1位置交换，就形成了"bac"这个字符串
我们可以遍历每个字符，再把它与每个字符尝试进行交换
所以我们可以写出以下代码
不过这个代码是错误的
我们在递归回溯的过程中，通常需要恢复现场
因为我们在这一层进行交换了后，回溯到上一层函数的话，就是拿交换后的字符串进行排序了，答案最终就不正确
所以我们要在每次递归完成后，恢复现场
我们这个代码还可以进行一个去重优化
设置一个boolused[]的数组，记录操作的字符如果某个字符没有出现，才进行操作
完整代码如下
vectorstringPrintAllPermutations(strings)
{
intindex=0;
vectorstringans;
_PrintAllPermutations(s,index,ans);
returnans;
}
void_PrintAllPermutations(strings,intindex,vectorstringans)
{
if(index==s.size())
{
ans.push_back(s);
return;
}
boolisUsed[]={0};
for(inti=index;is.size();i++)
{
if(!isUsed[(int)s[i]])
{
isUsed[(int)s[i]]=true;
Swap(s,index,i);
_PrintAllPermutations(s,index+1,ans);
Swap(s,index,i);
}
}
}
voidSwap(strings,intx,inty)
{
chartmp=s[x];
s[x]=s[y];
s[y]=tmp;
}