Leetcode 267 Solution

class Solution {
public:
    void generatePalindromes(string& curr, int from, vector<string>& res, char middle_ch)
    {
        if (from == curr.size())
        {
            string right = curr;
            reverse(right.begin(), right.end());

            string s = middle_ch == 0 ? curr + right : curr + string(1, middle_ch) + right;
            res.push_back(s);
            return;
        }

        unordered_set<char> visited;
        for (int i = from; i < curr.size(); i++)
        {
            if (visited.find(curr[i]) != visited.end())
                continue;

            visited.insert(curr[i]);
            swap(curr[i], curr[from]);
            generatePalindromes(curr, from + 1, res, middle_ch);
            swap(curr[i], curr[from]);
        }
    }

    vector<string> generatePalindromes(string s) {
        unordered_map<char, int> m;

        for (auto ch : s)
            m[ch]++;

        int evenCnt = 0;
        for (auto pair : m)
            evenCnt += pair.second % 2;

        vector<string> res;
        if (s.size() % 2 == 0 && evenCnt > 0 || s.size() % 2 == 1 && evenCnt > 1)
            return res;

        string curr;
        char middle_ch = 0;
        for (auto pair : m)
        {
            if (pair.second / 2)
                curr += string(pair.second / 2, pair.first);

            if (pair.second % 2 == 1)
                middle_ch = pair.first;
        }

        sort(curr.begin(), curr.end());

        generatePalindromes(curr, 0, res, middle_ch);

        return res;
    }
};