问题解构：LeetCode 267题“回文排列 II”要求生成给定字符串s所有可能的回文排列。核心挑战在于，首先需要判断字符串是否能构成回文排列（LeetCode 266题的基础），然后基于回文的对称特性，生成所有不重复的回文串。这本质上是排列生成与去重问题，适合用回溯算法解决。

方案推演：

1. 可行性判断：统计字符频率。要能构成回文，最多只能有一个字符出现奇数次（作为回文中心），其余字符必须出现偶数次。
2. 构造半串：取出所有出现偶数次的字符，将其频次减半，构成用于生成排列的字符集合。如果存在奇数次字符，则将其单独记录作为中心字符。
3. 生成排列：使用回溯法生成半串字符的所有不重复排列。这是关键，需要处理重复字符以避免生成相同的半串排列。
4. 镜像合成：将生成的每一个半串排列，加上中心字符（如果有），再拼接上其反转，即构成一个完整的回文串。

以下是完整的C++解决方案，包含详细注释。

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<string> generatePalindromes(string s) {
        vector<string> result;
        unordered_map<char, int> charCount;

        // 步骤1: 统计字符频率
        for (char c : s) {
            charCount[c]++;
        }

        // 判断是否能构成回文：奇数字符不能超过1个
        int oddCount = 0;
        char oddChar = 0;
        for (auto& [ch, cnt] : charCount) {
            if (cnt % 2 != 0) {
                oddCount++;
                oddChar = ch; // 记录可能的中心字符
            }
            if (oddCount > 1) return result; // 无法构成回文，直接返回空结果
        }

        // 步骤2: 准备用于生成排列的字符列表 (每个字符取一半数量)
        string halfChars;
        for (auto& [ch, cnt] : charCount) {
            halfChars.append(cnt / 2, ch); // 例如，'a'出现4次，则加入"aa"
        }

        // 步骤3: 回溯生成半串的所有不重复排列
        sort(halfChars.begin(), halfChars.end()); // 排序以便去重
        vector<bool> used(halfChars.size(), false);
        string currentHalf;
        backtrack(halfChars, used, currentHalf, oddChar, result);

        return result;
    }

private:
    void backtrack(const string& chars, vector<bool>& used, string& current, char midChar, vector<string>& result) {
        // 终止条件：当前半串长度等于可用字符数
        if (current.size() == chars.size()) {
            // 步骤4: 合成完整回文并加入结果
            string palindrome = current;
            if (midChar != 0) {
                palindrome += midChar;
            }
            // 拼接反转的半串
            palindrome += string(current.rbegin(), current.rend());
            result.push_back(palindrome);
            return;
        }

        for (int i = 0; i < chars.size(); ++i) {
            // 关键去重逻辑：如果当前字符与前一个相同，且前一个未被使用，则跳过
            // 这确保了相同字符在排列中不会产生重复序列
            if (used[i] || (i > 0 && chars[i] == chars[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            current.push_back(chars[i]);
            backtrack(chars, used, current, midChar, result);
            current.pop_back(); // 回溯
            used[i] = false;
        }
    }
};

算法核心逻辑与示例：

以输入字符串 "aabbc" 为例，演示算法流程：

1. 字符统计与判断：

   • charCount = {'a':2, 'b':2, 'c':1}
   • 奇数字符数 oddCount = 1 (字符 'c')，符合回文构成条件。oddChar = 'c'。

2. 构造半串字符集：

   • 对每个字符取 cnt/2：'a' -> "a", 'b' -> "b"。'c'的1次被中心占用，不加入半串。
   • halfChars = "ab"。排序后仍为 "ab"。

3. 回溯生成半串排列：

   • 从 "ab" 生成所有不重复排列："ab", "ba"。

4. 镜像合成完整回文：

   • 对于半串 "ab"，中心为 'c'，合成 "ab" + 'c' + "ba" = "abcba"
   • 对于半串 "ba"，中心为 'c'，合成 "ba" + 'c' + "ab" = "bacab"
   • 最终结果：["abcba", "bacab"]。

回溯过程中的去重机制详解：

当半串字符集包含重复字符时（例如 "aabb" 得到的 halfChars = "aabb"），标准的全排列会产生大量重复。代码中的关键去重判断为：

if (used[i] || (i > 0 && chars[i] == chars[i - 1] && !used[i - 1])) {
    continue;
}

其逻辑是：在当前位置选择字符时，如果当前字符与前一个字符相同，并且前一个相同的字符还没有被使用过，那么当前这个字符就不能被使用。这保证了在排列中，相同字符的相对顺序是固定的（总是使用第一个未被使用的），从而避免了生成 (a1, a2, b) 和 (a2, a1, b) 这样的重复序列。

复杂度分析：

• 时间复杂度：O((n/2)!)。最坏情况下（所有字符都出现偶数次且互异），需要生成半串字符的全排列。排序和字符统计为 O(n log n) 和 O(n)，但主导项是排列数。
• 空间复杂度：O(n)。用于存储字符频率的哈希表、用于回溯的标记数组used、当前路径current以及递归栈的深度，均与输入字符串长度n线性相关。

替代方案与性能对比：

除了回溯法，也可以使用C++标准库的 next_permutation 函数来生成排列，代码更简洁，但原理相同。

// 使用 next_permutation 的替代实现
vector<string> generatePalindromesSTL(string s) {
    vector<string> res;
    unordered_map<char, int> cnt;
    for (char c : s) ++cnt[c];
    string half, mid;
    int odd = 0;
    for (auto& [c, n] : cnt) {
        if (n % 2 == 1) {
            mid = c;
            ++odd;
        }
        half += string(n / 2, c);
        if (odd > 1) return res;
    }
    sort(half.begin(), half.end());
    do {
        string pal = half + mid + string(half.rbegin(), half.rend());
        res.push_back(pal);
    } while (next_permutation(half.begin(), half.end()));
    return res;
}

next_permutation 会自动处理重复元素的排列生成，但其内部实现同样需要排序并遵循特定的字典序生成规则，时间复杂度与回溯法同阶。回溯法的优势在于可以更早地进行剪枝（尽管本题剪枝空间不大），并且是理解排列类问题的通用范式。

参考来源

• LeetCode第267题_回文排列II
• LeetCode第266题_回文排列
• [LeetCode] 267. Palindrome Permutation II 回文全排列 II
• LintCode 267: minimum rest days (坐标型DP经典题)
• 终极LeetCode实战指南：如何利用开源项目高效刷题
• Leetcode 206. 反转链表（DAY 83） ---- Leetcode Hot 100总结