c++ 全排列问题 回溯方法,最好使用一个vector<bool>用来表示有没有使用过。去重也是需要注意的地方</bool>
class Solution {
public:
vector<string> ans;
string path="";
void backtracking(vector<char>& dic,vector<bool> used){
if(path.size()==dic.size()){
ans.push_back(path);
return;
}
for(int i=0;i<dic.size();i++){
if(used[i]) continue;
if(i>0&&dic[i]==dic[i-1]&&!used[i-1]) continue;
used[i]=true;
path.push_back(dic[i]);
backtracking(dic,used);
path.pop_back();
used[i]=false;
}
}
vector<string> Permutation(string str) {
vector<char> dic{str.begin(),str.end()};
vector<bool> used(str.size(),false);
sort(dic.begin(),dic.end());
backtracking(dic, used);
return ans;
}
};