面试题 08.07：无重复字符串的排列组合

输入：S = "qwe"
 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

输入：S = "ab"
 输出：["ab", "ba"]

class Solution {
public:
    string path;
    vector<string> res;
    void backtracing(string& S,vector<bool>& used){
        if(path.size()==S.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i<S.size();i++){
            if(used[i]==true) continue;
            used[i]=true;
            path.push_back(S[i]);
            backtracing(S,used);
            path.pop_back();
            used[i]=false;
        }
    }
    vector<string> permutation(string S) {
        vector<bool> used(S.size(),false);
        backtracing(S,used);
        return res;
    }
};

class Solution {
public:
    vector<string> permutation(string S) {
        string path;
        vector<string> res;
        vector<bool> used(S.size(),false);
        function<void()> backtracing=[&]{
            if(path.size()==S.size()){
                res.push_back(path);
                return;
            }
            for(int i=0;i<S.size();i++){
                if(used[i]==true) continue;
                used[i]=true;
                path.push_back(S[i]);
                backtracing();
                path.pop_back();
                used[i]=false;
            }
        };
        backtracing();
        return res;
    }
};