题解 | #字符串的排列#

回溯算法

class Solution {
public:
    vector<string> vec;
    string s = "";
    void Backtrack(string str, vector<bool> &used){
        if(s.size() == str.size()){
            vec.push_back(s);
            return;
        }
        for(int i = 0; i < str.size(); i++){
            if(i > 0 && str[i]==str[i-1] && used[i-1]==false)  continue;
            if(!used[i]){
                used[i] = true;
                s+=str[i];
                Backtrack(str, used);
                s.pop_back();
                //s.erase(s.end()-1);
                used[i] = false;
            }
        }
    }

    vector<string> Permutation(string str) {
        vec.clear();
        sort(str.begin(),str.end());
        vector<bool> used(str.size());
        Backtrack(str, used);
        return vec;
    }
};