C++中'AABC'字符串的回溯全排列实现问题求助

嘿，我懂你现在卡在带重复字符的全排列问题上了——普通的交换式全排列会输出一堆重复结果，而你已经想到用计数数组来控制字符使用次数，这个思路完全正确！我来帮你把剩下的代码补全，直接上可运行的完整实现，再拆解关键逻辑：

#include <iostream>
#include <string>
using namespace std;

// 定义字符集合：顺序对应计数数组的索引（A、B、C）
const string chars = "ABC";
// 计数数组：A剩余2个，B剩余1个，C剩余1个
int counters[] = {2, 1, 1};
// 排列的总长度：2+1+1=4
const int total_length = 4;

// 递归生成排列的函数
// current：当前已经构建好的部分排列字符串
void generateUniquePermutations(string current) {
    // 递归基条件：当前排列长度达到总长度，输出结果
    if (current.size() == total_length) {
        cout << current << endl;
        return;
    }

    // 遍历每一种字符类型
    for (int i = 0; i < 3; ++i) {
        // 如果当前字符还有剩余可用数量
        if (counters[i] > 0) {
            // 标记使用了一个该字符：减少计数
            counters[i]--;
            // 递归：把当前字符加入排列，继续构建下一位
            generateUniquePermutations(current + chars[i]);
            // 回溯：恢复计数，让后续分支可以使用该字符
            counters[i]++;
        }
    }
}

int main() {
    // 从空字符串开始生成排列
    generateUniquePermutations("");
    return 0;
}

• 计数数组的核心作用：counters 数组直接对应 chars 中每个字符的剩余可用次数，这样我们就不需要区分两个完全相同的'A'，只需要控制它的使用次数，从根源上避免了重复排列的生成。
• 回溯的必要性：每次递归调用后，必须把计数恢复——如果不做这一步，后续的循环分支会错误地认为该字符已经被用完，导致某些排列无法生成。
• 为什么能生成12种结果？：总排列数计算公式是 4!/(2!×1!×1!)=24/2=12，完全符合你的需求。

运行这段代码后，会输出所有12种不重复的排列：

AABC
AACB
ABAC
ABCA
ACAB
ACBA
BAAC
BACA
BCAA
CAAB
CABA
CBAA

内容的提问来源于stack exchange，提问作者Cantaff0rd