题解 | #字符串的排列#

回溯（深度优先搜索）。回溯求排列使用了一个标记数组used。最终的结果用set去重。

class Solution {
public:
    void dfs(string& str,vector<string>& result,string& path,vector<bool>& used){
        if(path.size()==str.size()){
            result.push_back(path);
            return;
        }
        for(int i=0;i<str.size();i++){
            if(used[i]) continue;
            used[i]=true;
            path.push_back(str[i]);
            dfs(str,result,path,used);
            path.pop_back();
            used[i]=false;
        }
    }
    
    vector<string> Permutation(string str) {
        vector<string> result{};
        string path{};
        vector<bool> used(str.size(),false);
        dfs(str, result, path, used);
        set<string> str_set{result.begin(),result.end()};
        vector<string> res{str_set.begin(),str_set.end()};
        return res;
    }
};