递归实现组合型枚举

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

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

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

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

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

数据范围
n>0 ,
0≤m≤n ,
n+(n−m)≤25

输入样例：

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 

老规矩，要找到所有的答案，就要想一个搜索的方法去查找，题目中有要求说了同一行的数要升序排列，也就是说

1 3 2

这种答案就不是合乎这道题的答案了，画出搜索树如下: 以n=5 m=3为例

代码实现如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int n,m;
const int N = 25;

int st[N];           //记录当前位置的状态
bool used[N];        //记录这个数字用过还是没用过

void dfs(int u)
{
    if(u == m){    //到达边界，进行输出
        for(int i = 0 ; i < m ; i++)
            printf("%d ", st[i]);
        puts("");
        return;
    }

    //后面的数字要比前面的数字大，所以从st[u-1]开始 u代表的是当前要填数字的位置
    for(int i = st[u-1] ; i < n ; i++){
        if(!used[i]){
            st[u] = i+1;   //给当前位置放一个值
            used[i] = true;    //记录这个数字已经被用过
            dfs(u+1);        //dfs下一个位置能放的数字

            st[u] = 0;        //回来之后要开始进行下一个位置的搜索之前恢复现场
            used[i] = false;
        }
    }
}

int main()
{
    cin >> n >> m;

    dfs(0);

    return 0;
}