题解 | #字符串的排列#

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;
    }
};