267. Palindrome Permutation II - cocoder39/coco39_LC GitHub Wiki

supposing len = s.length(), then str.length() = len / 2
as permutation
t(n) = O(n) + n * t(n - 1)
t(n - 1) = O(n) + (n - 1) * t(n - 2)
...
t(n) = n * O(n) + O(n!) = O(n !) 
total complexity is O((len/ 2)!)

class Solution {
public:
    vector<string> generatePalindromes(string s) {
        vector<int> count(256);
        for (auto c : s) {
            count[c]++;
        }
        
        int odd = 0;
        string center;
        string str;
        for (int i = 0; i < 256; i++) {
            if (count[i] % 2) {
                odd++;
                if (odd > 1) {
                    return {};
                }
                center.push_back(char(i));
            }
            str += string(count[i] / 2, char(i));
        }
        
        vector<string> res;
        string cur;
        vector<bool> visited(str.length());
        helper(res, cur, str, visited, center);
        return res;
    }
private:
    void helper(vector<string>& res, string& cur, string str, vector<bool>& visited, string center) {
        if (cur.length() == str.length()) {
            string rev = cur;
            reverse(rev.begin(), rev.end());
            res.push_back(cur + center + rev);
            return;
        }
        
        int len = str.length();
        for (int i = 0; i < len; i++) {
            if (visited[i] || (i > 0 && ! visited[i - 1] && str[i] == str[i - 1]))  continue;
            cur.push_back(str[i]);
            visited[i] = true;
            helper(res, cur, str, visited, center);
            cur.pop_back();
            visited[i] = false;
        }
    }
};