如何用C++高效实现从含重复字符的数组生成大小为N的唯一组合

核心思路 #

直接在组合生成阶段通过排序+回溯剪枝避免重复组合生成，从根源解决你遇到的两个问题，不需要事后去重，效率远高于生成全量组合后再去重的方案。

实现步骤 #

• 先对输入数组做升序排序，让相同值的元素相邻，为后续剪枝去重做基础，不受原数组顺序影响。
• 回溯生成组合时遵守两个规则：
  1. 每次仅选择当前起始索引之后的元素，保证组合内元素的索引严格递增，天然避免生成同组合的不同排列形式（比如不会出现TOMO和TMOO这类重复，因为选元素只能往后选，不会回头取前面的相同值元素）。
  2. 同一层回溯迭代中，如果当前元素和前一个元素值相同，直接跳过该元素，避免相同值的元素在同一层被重复选择，生成完全重复的组合。

完整实现代码 #

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

void backtrack(const vector<char>& arr, int n, int start, vector<char>& path, vector<string>& res) {
    // 路径长度达到n时存入结果
    if (path.size() == n) {
        res.emplace_back(path.begin(), path.end());
        return;
    }
    for (int i = start; i < arr.size(); ++i) {
        // 核心剪枝：同一层遇到相同元素直接跳过，避免重复组合
        if (i > start && arr[i] == arr[i-1]) {
            continue;
        }
        path.push_back(arr[i]);
        // 下一层从i+1开始选，保证不回头选元素，避免排列形式的重复
        backtrack(arr, n, i + 1, path, res);
        path.pop_back();
    }
}

vector<string> getUniqueCombinations(vector<char> arr, int n) {
    vector<string> res;
    if (n <= 0 || n > arr.size()) return res;
    // 先排序让相同元素相邻
    sort(arr.begin(), arr.end());
    vector<char> path;
    backtrack(arr, n, 0, path, res);
    return res;
}

// 测试用例
int main() {
    // 第一个测试用例
    vector<char> arr1 = {'A','B','C','C'};
    auto res1 = getUniqueCombinations(arr1, 2);
    cout << "N=2 结果：";
    for (auto& s : res1) cout << s << " "; // 输出 AB AC BC CC
    cout << endl;
    auto res2 = getUniqueCombinations(arr1, 3);
    cout << "N=3 结果：";
    for (auto& s : res2) cout << s << " "; // 输出 ABC ACC BCC
    cout << endl;

    // 第二个测试用例 TOMORROW
    vector<char> arr2 = {'T','O','M','O','R','R','O','W'};
    auto res3 = getUniqueCombinations(arr2, 4);
    cout << "TOMORROW N=4 结果数：" << res3.size() << endl;
    // 可自行遍历输出验证无重复
    return 0;
}

方案优势 #

• 完全解决你遇到的两个问题：排序适配任意原始输入顺序，索引递增选择规则避免排列类重复，同层剪枝避免值重复类重复。
• 效率更高：不需要生成全量组合再做去重操作，直接在生成阶段就剪掉了无效分支，内存和时间开销都远低于原方案，尤其适合数组长度大、重复元素多的场景。

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