Java转C++实现数组r元素组合时向vector传递子集问题求解

• 递归结果未正确承接：当前combinationUtil采用值传递resultSet，递归调用产生的新组合保存在副本中，调用侧未接收递归返回的resultSet，导致最终结果集为空。
• 不必要的拷贝开销：输入数组list、临时组合result、结果集resultSet全部采用值传递，每次递归都会产生全量拷贝，性能损耗极高。
• 缺少剪枝逻辑：原注释标注的剪枝条件未实现，当剩余可选元素数量不足以凑齐剩余需要的元素个数时，仍会执行无效递归。
• 元素插入逻辑冗余：使用insert向result指定位置插入元素完全没有必要，直接push_back追加到末尾即可实现相同效果，且可读性更高。

1. 调整combinationUtil的参数传递方式：list改为const vector<int>&避免数组拷贝，resultSet改为引用传递直接修改全局结果集，不需要再返回vector<vector<int>>。
2. 新增剪枝条件：当n - i < r - index时直接返回，终止无效递归。
3. 简化元素追加逻辑，选择元素后push_back，回溯前pop_back还原临时组合状态。
4. 递归调用不需要接收返回值，直接修改引用传递的结果集即可。

#include <vector>
using namespace std;

void combinationUtil(const vector<int>& list, int n, int r, int index, vector<int>& result, int i, vector<vector<int>>& resultSet) {
    // 当前组合长度符合要求，加入结果集
    if (index == r) {
        resultSet.push_back(result);
        return;
    }
    // 剪枝：剩余元素不足，直接返回
    if (n - i < r - index) {
        return;
    }
    // 越界判断
    if (i >= n) {
        return;
    }
    // 选择当前元素
    result.push_back(list[i]);
    combinationUtil(list, n, r, index + 1, result, i + 1, resultSet);
    // 回溯：不选择当前元素
    result.pop_back();
    combinationUtil(list, n, r, index, result, i + 1, resultSet);
}

vector<vector<int>> getCombinations(const vector<int>& list, int r) {
    vector<vector<int>> resultSet;
    vector<int> temp;
    combinationUtil(list, list.size(), r, 0, temp, 0, resultSet);
    return resultSet;
}

#include <iostream>
int main() {
    vector<int> arr = {1,2,3,4,5};
    int r = 3;
    auto combinations = getCombinations(arr, r);
    for (auto& comb : combinations) {
        for (int num : comb) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

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