1011 - 实现组合型枚举

要实现组合型枚举，可以采用位运算和二进制状态压缩的思想。首先，我们需要一个递归函数来进行枚举。该函数将有三个参数，分别是总的递归次数u，有效的递归次数sum和状态压缩变量state。在递归函数中，我们需要判断sum是否等于m，如果等于m，则输出当前的状态，并结束递归。否则，我们判断u是否等于n，如果等于n，则结束递归。接下来，我们可以对当前位进行两种操作：选中或不选中。选中则将当前位置为1，并递归调用下一层。不选中则保持当前位不变，并递归调用下一层。最后，在主函数中，我们需要读取输入的n和m，并调用递归函数进行枚举。

例如，对于输入样例5 3，我们可以得到如下结果：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

其中，每一行表示一种组合型枚举的结果，数字之间用空格分隔。

相关问题

pta7-5 h0093-递归实现组合型枚举

题目描述

输入两个正整数 n≤m≤10，输出从 n 个不同元素中取出 m 个元素组成的组合，按照字典序从小到大输出所有组合。

输入格式
两个正整数 n，m。

输出格式
每行输出一种组合。

数据范围
1≤n≤m≤10

输入样例：
4 2
输出样例：
1 2
1 3
1 4
2 3
2 4
3 4

算法1

C++ 代码

递归实现组合型枚举c++

递归是一种解决问题的技术，在C++中常用于处理需要重复执行相似任务的情况，特别是涉及到树形结构或序列排列的问题，比如组合型枚举。在C++中，如果要递归地生成所有可能的组合，可以使用回溯算法或深度优先搜索（DFS），尤其是在处理排列组合的计算时。

例如，为了生成从n个不同元素中取出k个元素的所有组合，你可以定义一个函数`generateCombinations`，它接受当前选择的元素数、剩余的元素集合以及已经构建出的组合结果。这个函数的基本逻辑会包含以下步骤：

1. **基本情况**：当选择的元素数达到k时，将当前组合添加到结果集中，并返回继续下一轮递归。
2. **递归情况**：遍历剩余的元素，对每一个元素，尝试将其加入当前组合，然后减少剩余元素数并递归调用自身。
3. **回溯**：递归结束后，恢复状态，尝试下一个元素。

这是一个简单的示例代码片段，展示了如何递归地生成组合：

#include <iostream>
#include <vector>

void generateCombinations(const std::vector<int>& elements, int k, int start = 0,
                          std::vector<int>& combination = {}) {
    if (combination.size() == k) {
        // 基本情况：组合完成，打印出来
        for (int num : combination)
            std::cout << num << " ";
        std::cout << "\n";
        return;
    }
    
    // 递归情况：尝试所有可能的选择
    for (size_t i = start; i < elements.size(); ++i) {
        combination.push_back(elements[i]);
        generateCombinations(elements, k, i + 1, combination);
        // 回溯：撤销这次选择
        combination.pop_back();
    }
}

int main() {
    std::vector<int> elements = {1, 2, 3};
    int k = 2;
    generateCombinations(elements, k);
    return 0;
}