题解 | #字符串的排列#

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<bool> used(str.size(), false);
        backtracking(str, used);

        return res;
    }

    string path;
    vector<string> res;
    void backtracking(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] || (i>0 && used[i-1] && s[i]==s[i-1]))
                continue;

            path.push_back(s[i]);
            used[i] = true;
            backtracking(s, used);
            used[i] = false;
            path.pop_back();
        }
    }
};