#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class Solution {
public:
vector<string> permutation(string S) {
sort(S.begin(),S.end());
vector<string> retVec;
vector<int> used_posVec(S.size());
string cur_S;
recursive(retVec,S,cur_S,1,used_posVec);
return retVec;
}
/** 采用深度优先搜索 + 分支限界的方式****/
void recursive(vector<string> &retVec, string &sort_S,string &cur_S,int cur_index,vector<int> &used_posVec){
if(cur_index == sort_S.size()) //递归叶子节点，递归终止
{
//查看当前还有哪个字符没有被使用
for(int i = 0;i < used_posVec.size();i++)
if(!used_posVec[i]) {
cur_S.push_back(sort_S.at(i));
retVec.push_back(cur_S); //诞生一种新的情况
cur_S.pop_back();
}
}else{
char last_try_char = 0; // 上一个被当前位置使用的字符是什么
for(int i = 0;i < used_posVec.size();i++){
cur_S.push_back(sort_S.at(i));
if(!used_posVec[i] && last_try_char != sort_S.at(i)) // 该字符在这个位置没有被使用，并且不等于上一个在该位置尝试过的字符
{
used_posVec[i] = 1;
recursive(retVec,sort_S,cur_S,cur_index+1,used_posVec);
used_posVec[i] = 0;
last_try_char = sort_S.at(i);
}
cur_S.pop_back();
}
}
}
};
int main(){
Solution s;
vector<string> retVec = s.permutation("abccc");
for(auto it = retVec.begin();it!=retVec.end();it++){
cout<<*it<<endl;
}
return 1;
}