题解 | #字符串的排列#

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    vector<string> ans;
    //unordered_set<string> ans; set去重之后无法直接返回
    string path;
    void backTracking(string &str,vector<bool> used)
    {
        if(path.size()==str.size())
        {
            ans.push_back(path);
            return;
        }
        for(int i=0;i<str.size();i++)
        {    //used[i]==true表示同一个集合里即树枝上收集过
            //str[i]==str[i-1] && used[i-1]==false去重，同一个树层上收集过
            if(used[i]==true|| (i>0 && str[i]==str[i-1] && used[i-1]==false))
            { continue; }            
            path+=str[i];
            used[i]=true;
            backTracking(str,used);
            path.pop_back();
            used[i]=false;
        }
    }
    vector<string> Permutation(string str) {
        if(str.size()==0) return ans;
        sort(str.begin(),str.end()); //字符串内的字符进行排序之后，相同的元素则在一起，这时候去重才有效
        vector<bool> used(str.size(),0);
        backTracking(str,used);
        return ans;
        // write code here
    }
};

回溯算法。使用used数组去判断纵向树枝中当前遍历元素是否已经加入路径中，used再去判断横向树层中是否已经收集过。