C++实现：如何生成数字向量中长度为N的无排列重复组合

问题描述 #

需要从包含0-9数字的vector中选取m个数字，组成长度为m的数，但同一组数字的不同排列视为同一组合，仅输出其中一个（例如1234、4321视为同一组合，只输出一次）。现有递归代码会生成所有排列，无法满足需求，需要修改实现逻辑。

现有代码核心问题：原递归函数的for循环从索引0开始遍历整个可用数字集合，导致同一组数字的不同排列被多次生成——比如先选1再选2，和先选2再选1，会生成12和21两个结果，不符合组合要求。

解决方案思路 #

要避免生成重复排列的组合，核心是控制选择数字的顺序：每次递归选择数字时，只从当前位置的下一个元素开始选取，确保不会回头选择之前已经跳过的元素。这样生成的结果只会是原集合中元素的顺序组合，不会出现逆序的重复排列。

修改后的代码 #

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

int n = 0, m = 0, temp;
vector<int> given;
vector<int> num;

// 新增start参数控制遍历起始位置，避免重复选之前的元素
void generate(int start, int m) {
    if (m == 0) {
        for (int x : num) {
            cout << x;
        }
        cout << '\n';
        return;
    }
    // 从start开始遍历，而非从0开始
    for (int i = start; i < given.size(); i++) {
        num.push_back(given[i]);
        // 递归时起始索引改为i+1，确保下一次只选当前元素之后的数字
        generate(i + 1, m - 1);
        num.pop_back(); // 回溯，撤销当前选择
    }
}

int main () {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        given.push_back(temp);
    }
    cin >> m;
    // 初始调用时起始索引为0
    generate(0, m);
    return 0;
}

关键改动说明 #

1. 递归参数优化：新增start参数，明确每次遍历的起始位置，避免重复选择已处理过的元素。
2. 遍历范围调整：for循环从start开始，而非固定从0开始，确保选择逻辑按原集合顺序推进。
3. 递归调用逻辑：递归时传递i+1作为新的起始索引，保证下一层递归只能选当前元素之后的数字，彻底杜绝同一组合的不同排列生成。

例如，当给定集合为[1,2,3]、m=2时，只会输出12、13、23，不会出现21、31、32这类重复排列的组合。

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