面试题 08.08. 有重复字符串的排列组合

class Solution {
public:
    string tmp;
    vector<bool>used;
    vector<string>res;
    
    vector<string> permutation(string S) {
        used=vector<bool>(S.size(),false);
        sort(S.begin(),S.end());
        dfs(0,S);
        return res;
    }
    
    void dfs(int k,string &S){
        if(k==S.size()){
            res.push_back(tmp);
            return ;
        }
        
        for(int i=0;i<S.size();i++){
            if(used[i])continue;
            if(i && S[i]==S[i-1] && used[i-1])continue;
            used[i]=true;
            tmp.push_back(S[i]);
            dfs(k+1,S);
            used[i]=false;
            tmp.pop_back();
        }   
    }
};