题目描述

给定集合{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

算法1

(暴力枚举) $O(2^n)$

没仔细看题，还以为有特判，哭泣哭泣

逻辑和92完全一样，只不过需要过滤子集，增加一个状态参数，更换一下递归顺序

C++ 代码

/*
    Name:AcWing 93. 递归实现组合型枚举
    Author:wyz
    Date:2019/4/2 10:27:42
    Note:

*/

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
int n,m;
void dfs(int cur,int total,int station){ 
    //cur表示当前要对cur进行选择放入说着不放入
    //station表示对于所有小于cur的数的抉择情况(放入或者不放入)
    //状态参数新增total表示一共选择的数的个数 
    //由于cur是不断累加的，总是小数先放入，所以必然升序 
    if(cur>n){//已经挑完了所有的数，结束递归 
        if(total==m){//对于所有子集，过滤正好选择了m个数的子集 
            int count=0;//表示第x个数字 
            while(station){
                count++;
                if(station&1)cout<<count<<" ";//如果末位是1，说明当前子集包含该数，并输出 
                station>>=1;//遍历下一位 
            }
            cout<<endl;
        }
        return;
    }
    //因为每次都是选择放入，所以第一个输出即是原集 
    dfs(cur+1,total,station);//该集合不包含cur
    dfs(cur+1,total+1,station | 1 << (cur-1) );//该集合包含cur
    return;

}
int main(){
    cin>>n>>m;
    dfs(1,0,0);//从1~n以此进行选择，此时表示对1进行选择，并且当前的状况是集合为空
    return 0;
}