题解 | #字符串的排列#

#include <string>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    vector<string> Permutation(string str) {
        // write code here
        vector<string>ans;
        string combine;
        vector<int>vis;
        vis.resize(str.size());
        sort(str.begin(),str.end());
        backtrack(ans, combine, vis, str, 0);
        return ans;

    }

    void backtrack(vector<string>&ans,string combine,vector<int>&vis,string str,int idx){
        if(idx==str.size()){
            ans.push_back(combine);
        }

        
        for(int i=0;i<str.size();++i){
            if(vis[i]||(i>0&&str[i]==str[i-1]&&!vis[i-1])){
                continue;
            }
            combine.push_back(str[i]);
            vis[i]=1;
            backtrack(ans, combine, vis, str, idx+1);
            combine.pop_back();
            vis[i]=0;
            
        }

    }
};