题解 | #字符串的排列#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    vector<string> Permutation(string str) {
        // write code here
        vector<string> res;
        set<string> existsstr;
        int n = str.size();
        backtrace(res, existsstr,0,n,str);
        return res;
    }

    void backtrace(vector<string> &res,set<string> &existsstr, int first, int n, string str){
        if(first == n){
           if(existsstr.find(str) == existsstr.end()){
                res.push_back(str);
                existsstr.insert(str);
            } 
        }
        else{
            for(int i=first ;i<n;i++){
                int temp = str[first];
                str[first] = str[i];
                str[i] = temp;
                backtrace(res, existsstr, first+1, n, str);
                temp = str[first];
                str[first] = str[i];
                str[i] = temp;
            }
            
        }
    }
};