递归实现组合型枚举

题目介绍（来自acwing93. 递归实现组合型枚举 - AcWing题库）:

从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

输入格式

两个整数 n,m ,在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围

n>0
0≤m≤n
n+(n−m)≤25

这道题的常规解法是递归，接下来我们来贴一下代码：

#include<iostream>

using namespace std;

const int N=1000;
int a[N];
bool st[N];
int n,m;

void dfs(int u,int k)
{
    if(k==m+1)
    {
        for(int i=1;i<k;i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
        return ;
    }
    else if(u==n+1)
    {
    	return ;
	}
    a[k]=u;
    dfs(u+1,k+1);
    a[k]=0; 
    dfs(u+1,k);
}

int main()
{
    cin>>n>>m; 
    dfs(1,1);
    
    return 0;
}

首先，我们来理清一下题意，如果大家学过高中数学，就一定知道组合的概念，不知道的可以搜一下，这里就不再赘述，总之这题是求n个数中选m个数的所有组合

在代码中的u表示所选的数，k表示已经选的数的数

举个例子大家或许能明白一些，以5 3举例：

这就是我们递归的过程

其中：

{

a[k]=u;

dfs(u+1,k+1);

a[k]=0;
}

 是表示选u，之后“a[k]=0”再还原现场

{

dfs(u+1,k);
}

则是跳过u,不选

接下来的"k==m+1"表示已经选了m个数，然后就可以输出了

但是会遇到一些特殊情况

例如上述例子中

若我们已经选到1 2 5

由于前面我们只考虑了u<=m的情况，所以接下选完1 2 5后u继续往前加

就可能出现1 2 6,1 2 7等等的情况

所以，我们还要判断一下u的边界

加上这段代码

else if(u==n+1)
{
        return ;
}

就可以解决问题了