题目描述

从 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

(我的代码) 复杂度应该不太高

菜鸟写dfs因为一开始是从走迷宫开始学起的，所以每次写的时候都喜欢加上for循环，这种其实非常的不好用，但是扩展起来好多问题都能做
加上位运算是因为第一节课学的位运算
dfs四个变量分别是，现在遍历到第几个数字的cnt，已经被遍历过的数据中最小的数值，加入到选中数字中的数字，state存的就是那些数据被存进去了

时间复杂度分析：n^2

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
void dfs(int cnt,int minn, int num,int state){
    if(n-cnt+num < m)return;
    if(num == m){
        //cout<<state<<endl;
        for(int i  = 0 ; i < n ; i ++){
                if((state >> i) & 1){
                    cout<<i+1<<" ";
                }
        }
        cout<<endl;
        return ;
    }
    if(cnt >= n)return;
    for(int i = minn ;i < n;i++){
        if(!((state & (1<<i)) >> i))
        {
        int t = state;
        state = state | (1<<i);
        dfs(cnt+1,i,num+1,state);
        state = t;
        }
    }
}
int main(){
    scanf("%d %d",&n,&m);
    dfs(0,0,0,0);
}

能过真是奇迹！