算法题（172）：组合型枚举

审题：
本题需要我们对1到n的数进行n中取m的组合枚举，找到所有不同的组合并按照字典序输出，要求行内和行间都满足字典序

思路：
本题我们采用枚举的方法，但是用for循环暴力枚举会有两个大问题

其一是无法确定for循环个数，因为我们要取m次，而m是题目给的，我们事先无法知道

其二是较难进行字典序排序输出

其三是for循环层数可能极大，会超时

所以我们采用深度优先搜索的方法进行枚举

方法一：深度优先搜索

我们先分析选取过程与方法：

我们以从1~4中选三个数的情况为例：
对于第一个空位：我们可以填写1,2,3,4

对于已经选了1的第二个空位我们可以填写：2,3,4

对于已经选了2的第二个空位我们可以填写：3,4

对于已经选了3的第二个空位我们可以填写：4

对于已经选了4的第二个空位我们不可以填写，直接返回不输出

.......

发现：

1.我们需要从前面填写过的数的下一个数开始填写，且这个数的填写顺序是字典序从小到大

eg：前面有了14_,后面如果填写41_会出现重复，而我们需要的是组合不是排列

字典序从小到大是为了让行内满足字典序要求

2.当无法插入足够个数的数时，直接return不输出

3.当插入个数等于m时：按格式输出数据并返回

解题：

#include<iostream> #include<vector> using namespace std; int n, m; vector<int> path;//记录数据 void dfs(int begin) { if (path.size() == m) { for (auto e : path) cout << e << " "; cout << endl; return; } for(int i = begin; i <= n; i++) { path.push_back(i);//插入当前层选取数据 dfs(i + 1);//进入更深一层搜索 path.pop_back();//数据回溯 } } int main() { cin >> n >> m; dfs(1);//搜索 return 0; }

注意：
1.使用vector进行数据记录的好处：不用在dfs中传递待插入位置的索引，可以直接使用push_back()接口进行数据插入，使用pop_back()接口进行数据弹出回溯。

且还可以直接根据path的size判断是否插入足够数据

2.由于我们要知道当前层是从哪个数开始放置，所以一定要传一个begin给dfs函数

P10448 组合型枚举 - 洛谷