每日一题：无重复字符串的排列组合

题目：无重复字符串的排列组合

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

示例2

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

分析

经典的回溯问题，题目要求字符串的每个字符都不相同，我刚开始认为输入字符串可能有重复的字符，所以加个段去重的代码，最后提交时候发现不去重也可以测试通过。

代码

class Solution {
public:
    vector<string> permutation(string S) {
        {// 多余的
            sort(S.begin(), S.end());
            auto it = std::unique(S.begin(), S.end());
            S.resize(std::distance(S.begin(), it));
        }
        string path;
        used.resize(S.size(), false);
        dfs(S, path);
        return ret;
    }

    vector<string> ret;
    vector<bool> used;
    void dfs(string& S, string& path) {
        if (path.size() == S.size()) {
            ret.push_back(path);
            return;
        }

        for (int i = 0, size = S.size(); i < size; ++i) {
            if (used[i]) continue;
            used[i] = true;
            path.push_back(S[i]);
            dfs(S, path);
            used[i] = false;
            path.pop_back();
        }
    }

};

  代码精进之路，我们一起成长！