题目描述

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

非递归思路

1.我们来看样例 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到(1<<5)-1

5 3
    1--00001
    2--00010
    3--00011
1 2 3
    4--00100
    5--00101
1 2 4
    6--00110
1 2 5
    7--00111
    8--01000
    9--01001
1 3 4
   10--01010
1 3 5
   11--01011
   12--01100
1 4 5
   13--01101
   14--01110
   15--01111
   16--10000
   17--10001
2 3 4
   18--10010
2 3 5
   19--10011
   20--10100
2 4 5
   21--10101
   22--10110
   23--10111
   24--11000
3 4 5
   25--11001
   26--11010
   27--11011
   28--11100
   29--11101
   30--11110
   31--11111

我们可以发现0出现的位置和我们要求的数列有关！！！

算法1

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,x) memset(a,x,sizeof(a))
#define SZ(x) ((int)(x).size())
#define lson rt<<1
#define rson rt<<1|1
#define pb push_back
#define fi first
#define se second
#define what_is(x) cerr<<#x<<" "<<x<<endl;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
template <typename T>
inline void _read(T& x){
    cin>>x;
}
void R(){}
template <typename T,typename... U>
void R(T&head,U&... tail){
    _read(head);
    R(tail...);
}

template <typename T>
inline void _write(const T& x){
    cout<<x<<' ';
}
void W(){cout<<endl;}
template <typename T,typename... U>
void W(const T&head,const U&... tail){
    _write(head);
    W(tail...);
}
template<typename T>
void debug(vector<T> V){
    for(auto x:V){
        cout<<x<<" ";
    }
    cout<<endl;
}
void go();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //cout<<fixed<<setprecision(8);
    go();
    return 0;
}
/*************************************/
int n,m;
void check(int x){
    int xx=(1<<n)-1;
    xx=xx^x;//取反
    int num=0;
    while(xx){
        num++;
        xx-=xx&-xx;
        if(num>m){
            return;
        }
    }//求1的个数
    if(num!=m){
        return;
    }
    vi ans;
    per(i,n-1,0){
        if(((x>>i)&1) == 0){
            ans.pb(n-i);
        }
    }
    for(auto x:ans){
        cout<<x<<" ";
    }
    cout<<endl;
}
void go(){
    R(n,m);
    rep(i,1,(1<<n)-1){
        check(i);
    }
}