LeetCode 面试题 08.08. 有重复字符串的排列组合

解法一：

class Solution {
public:
    vector<string> permutation(const string& S) {
        int len = S.length();
        set<string> strs;
        vector<vector<char>> perms = permute(vector<char>(S.begin(), S.end()));
        for (auto& i : perms) {
            strs.insert(string(i.begin(), i.end()));
        }

        return vector<string>(strs.begin(), strs.end());
    }
private:
    template <class T>
    vector<T> rotate_imp(const vector<T>& nums, int n) {
        vector<T> ret;
        int sz = (int)nums.size();
        for (int i = 0; i < sz; ++i) {
            ret.emplace_back(nums[(i + n) % sz]);
        }
        return ret;
    }
    template <class T>
    vector<vector<T>> rotate(const vector<vector<T>>& per) {
        vector<vector<T>> ret;
        for (auto& i : per) {
            for (int j = 0; j < i.size(); ++j) {
                ret.emplace_back(rotate_imp(i, j));
            }
        }
        return ret;
    }
    template <class T>
    vector<vector<T>> permute(const vector<T>& nums) {
        vector<vector<T>> ret{{}};
        for (auto& i : nums) {
            for (auto& j : ret) j.emplace_back(i);
            
            ret = rotate(ret);
        }
        return ret;
    }
};

解法二：

class Solution {
public:
    vector<string> permutation(string& S) {
        backtrack(S);
        return rst;
    }
private:
    void backtrack(string& S, int start = 0) {
        int len = (int)S.length();
        if (len == start) {
            rst.emplace_back(S);
            return;
        }
        set<char> vis;
        for (int i = start; i < len; ++i) {
            if (vis.find(S[i]) == vis.end()) {
                vis.insert(S[i]);
                swap(S[i], S[start]);
                backtrack(S, start + 1);
                swap(S[i], S[start]);
            }
        }
    }
private:
    vector<string> rst;
};

解题思路

难点1：全排列的题，归根揪底，需要手动实现permute，无非两种实现方式，一种是使用递归进行回溯，另一种是直接for循环进行轮换；

难点2：解法一使用轮换实现了全排列的基础算法，做成了模板函数进行使用；set去重即可；

难点3：解法二使用的回溯+剪枝，使用set进行剪枝去重；回溯的话，掌握回溯的基本结构即可灵活运用；

难点4：总的来讲，这道题不掌握套路，直接上手撸还是蛮难的；

知识点：

知识点1：STL中next_permutation的用法（自动去重，用前需要进行排序）；

class Solution {
public:
    vector<string> permutation(string S) {
        vector<string> res;
        string path;
        sort(S.begin(), S.end());
        do{
            for(int i = 0; i < S.size(); i++){
                path += S[i];
            }
            res.push_back(path);
            path = {};
        }while(next_permutation(S.begin(), S.end()));
        return res;
    }
};

知识点2：回溯算法的基本框架；参考回溯算法详解;

// result = []
// def backtrack(路径, 选择列表):
//     if 满足结束条件:
//         result.add(路径)
//         return

//     for 选择 in 选择列表:
//         做选择
//         backtrack(路径, 选择列表)
//         撤销选择