题解 | #NC-121 字符串的全排列#

class Solution {
public:
    
    void func(vector<string>& res, string& str, int begin){
        if(begin == str.size()-1){
            if(find(res.begin(), res.end(), str) == res.end()){  // 避免“aa”的重复出现
                res.push_back(str);
//                 cout << str << endl;
            } //  结果去重
                
            return;
        }
        // 当begin为 i 时，遍历数组使每个元素放在第 i 个位置一次，得到此时他们的子串的全排列
        // 直到begin为len-1时，此时每个元素都已经在数组的每个位置出现了一次，所以得到最后一个全排列
        
//         for(int i = 0; i < str.size(); i++) // i 不需要从0开始
        for(int i = begin; i < str.size(); i++){ // i 从begin开始就不会有重复全排列出现
            swap(str[i], str[begin]);
            func(res, str, begin+1); // 对子串进行相同操作
            swap(str[i], str[begin]); // 恢复原来的字符串，进行下一个元素的全排列
        }
    }
    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.empty())
            return res;        
        func(res, str, 0);
        sort(res.begin(), res.end());
        return res;
    }
};