题解 | 字符串的排列

class Solution {
  public:
    vector<string> Permutation(string str) {
        vector<string> result;
        if (str.empty()) return result;

        // 对字符串排序，便于去重
        sort(str.begin(), str.end());
        vector<bool> used(str.size(), false);
        string path;
        backtrack(str, used, path, result);
        return result;
    }

  private:
    void backtrack(const string& str, vector<bool>& used, string& path,
                   vector<string>& result) {
        // 终止条件：当前路径长度等于原字符串长度
        if (path.length() == str.length()) {
            result.push_back(path);
            return;
        }

        for (int i = 0; i < str.length(); i++) {
            // 跳过已使用的字符
            if (used[i]) {
                continue;
            }

            // 去重：如果当前字符与前一个字符相同，且前一个字符未被使用，则跳过
            // 这样可以避免生成重复的排列
            if (i > 0 && str[i] == str[i - 1] && !used[i - 1]) {
                continue;
            }

            // 做出选择
            used[i] = true;
            path.push_back(str[i]);

            // 递归
            backtrack(str, used, path, result);

            // 撤销选择
            path.pop_back();
            used[i] = false;
        }
    }
};

本题与有重复数字全排列的相似性
两者确实非常相似：
相同点：
都使用回溯算法框架
都需要处理重复元素/字符的问题
都使用排序+跳过重复元素的策略来去重
都使用标记数组来记录已使用的元素

不同点：
输入类型不同：一个是数字数组，一个是字符串
输出格式不同：一个返回数字列表的列表，一个返回字符串列表