如何获取多层std::vector的子向量全组合？递归实现方案咨询

你说得没错，递归确实是处理这种任意数量集合的笛卡尔积问题的最佳方案——毕竟当外层vector的长度不固定时，硬写多层for循环根本不可能，递归能完美适配任意规模的输入。

核心思路 #

你的需求本质是求多个集合的笛卡尔积：外层std::vector中的每个子std::vector就是一个集合，我们需要从每个集合里选一个元素，生成所有可能的组合。递归的逻辑很清晰：

• 用一个变量跟踪当前处理到外层vector的第几个元素
• 维护一个临时向量保存当前正在构建的组合
• 当处理完所有外层元素时，把临时组合加入结果
• 否则，遍历当前层的所有元素，把元素加入临时组合后递归处理下一层，处理完回溯（移除当前元素）以尝试下一个可能

C++ 实现代码 #

下面是完整的模板化实现，适配任意元素类型和任意规模的输入：

#include <vector>
#include <iostream>

// 递归辅助函数：处理核心逻辑
template <typename T>
void generateCombinationsHelper(
    const std::vector<std::vector<T>>& input,
    size_t currentIndex,
    std::vector<T>& currentCombination,
    std::vector<std::vector<T>>& result) {
    // 递归终止：所有外层元素都处理完毕，保存当前组合
    if (currentIndex == input.size()) {
        result.push_back(currentCombination);
        return;
    }

    // 遍历当前外层元素的所有子元素，逐个尝试加入组合
    for (const T& element : input[currentIndex]) {
        currentCombination.push_back(element);
        // 递归处理下一个外层元素
        generateCombinationsHelper(input, currentIndex + 1, currentCombination, result);
        // 回溯：移除当前元素，准备尝试当前层的下一个元素
        currentCombination.pop_back();
    }
}

// 对外接口函数：初始化变量并调用递归
template <typename T>
std::vector<std::vector<T>> generateAllCombinations(const std::vector<std::vector<T>>& input) {
    std::vector<std::vector<T>> result;
    std::vector<T> currentCombination;
    generateCombinationsHelper(input, 0, currentCombination, result);
    return result;
}

// 辅助打印函数：针对你的vector<vector<int>>场景
void printIntVectorCombinations(const std::vector<std::vector<std::vector<int>>>& combinations) {
    for (const auto& combo : combinations) {
        std::cout << "{";
        for (size_t i = 0; i < combo.size(); ++i) {
            std::cout << "{" << combo[i][0] << "," << combo[i][1] << "}";
            if (i != combo.size() - 1) std::cout << ",";
        }
        std::cout << "} ";
    }
    std::cout << "\n";
}

int main() {
    // 测试第一个示例输入
    std::vector<std::vector<std::vector<int>>> test1 = {{{0,0},{1,1}},{{2,2},{3,3}},{{4,4},{5,5}}};
    auto result1 = generateAllCombinations(test1);
    std::cout << "第一个测试用例结果：\n";
    printIntVectorCombinations(result1);

    // 测试第二个示例输入
    std::vector<std::vector<std::vector<int>>> test2 = {{{0,0},{1,1},{2,2}},{{3,3},{4,4},{5,5}},{{6,6},{7,7},{8,8}}};
    auto result2 = generateAllCombinations(test2);
    std::cout << "\n第二个测试用例结果（前6个）：\n";
    for (size_t i = 0; i < 6 && i < result2.size(); ++i) {
        std::cout << "{";
        for (size_t j = 0; j < result2[i].size(); ++j) {
            std::cout << "{" << result2[i][j][0] << "," << result2[i][j][1] << "}";
            if (j != result2[i].size() - 1) std::cout << ",";
        }
        std::cout << "} ";
    }
    std::cout << "\n共生成 " << result2.size() << " 个组合\n";

    return 0;
}

代码说明 #

1. 模板化设计：不管你的元素是vector<int>、string还是自定义类型，只要支持拷贝，就能直接使用这个函数。
2. 递归与回溯：递归负责逐层处理，回溯确保我们能遍历当前层的所有可能元素，不会遗漏组合。
3. 适配任意规模：外层vector的长度（集合数量）、每个子vector的长度（集合元素数量）都可以任意变化，不需要修改代码。
4. 时间复杂度：O(N₁×N₂×…×Nₖ)，其中Nₖ是第k个外层子vector的元素数，这是生成笛卡尔积的最优复杂度——毕竟必须遍历所有可能的组合。

运行结果 #

第一个测试用例会输出你期望的8个组合，第二个测试用例会生成3×3×3=27个组合，完全符合你的需求。

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