力扣（LeetCode）267. 回文排列 II（2022.09.24）

给定一个字符串 s ，返回 其重新排列组合后可能构成的所有回文字符串，并去除重复的组合 。

你可以按 任意顺序 返回答案。如果 s 不能形成任何回文排列时，则返回一个空列表。

示例 1：

输入: s = “aabb”
输出: [“abba”, “baab”]
示例 2：

输入: s = “abc”
输出: []

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-permutation-ii

方法一：回溯

C++提交内容：

class Solution {
    vector<string> ans;
public:
    vector<string> generatePalindromes(string s) {
        vector<int> cnts(26);
        for (char c : s) cnts[c - 'a']++;  // 统计每个字符出现的个数
        string s1, oddChar;
        for (int i = 0, odd = 0; i < 26; i++) {
            if (cnts[i] % 2) {
                oddChar += ('a' + i);
                if (++odd > 1) return ans;  // 如果奇数字符个数 > 1, 则不可能构成回文串
            } 
        }
        for (int i = 0; i < 26; i++) s1 += string(cnts[i] / 2, ('a' + i));
        string s2 = s1;
        do {
            string str = s2;
            reverse(str.begin(), str.end());
            ans.push_back(s2 + oddChar + str);           
            next_permutation(s2.begin(), s2.end());
        } while (s2 != s1);
        return ans;
    }
};