题解 | #字符串的排列#

• 对字符串进行排序，用于后续剔除重复排序；
• 采用递归+回溯，当组合长度等于字符串长度时，将该组合放入结果并返回；
• 如果本层已使用过相同原始，跳过本次组合；
• 如果当前元素还未使用过，则将该元素放入本次组合，继续进行本次组合，返回后弹出该元素继续进行其他组合；
• 所有情况遍历完成后，返回最终排列结果。

class Solution {
public:
    void backtracking(string& s,vector<bool>& visited, vector<string>& res, string& path) {
        if (path.size() == s.size()) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < s.size(); i++) {
            if (i > 0 && s[i] == s[i - 1] && visited[i - 1] == false) {
                continue;
            }
            if (visited[i] == false) {
                visited[i] = true;
                path.push_back(s[i]);
                backtracking(s, visited, res, path);
                path.pop_back();
                visited[i] = false;
            }
        }
    }
    vector<string> Permutation(string str) {
        vector<string> result;
        vector<bool> visited(str.size(), false);
        string path;
        sort(str.begin(), str.end());
        backtracking(str, visited, result, path);
        return result;
    }
};