从零开始学算法-Day4

//2020.4.24 第四天了

题目：递归实现组合型枚举

链接：https://ac.nowcoder.com/acm/contest/998/B
来源：牛客网

题目描述从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。n>0,n0≤m≤n, n+(n−m)≤25。

求解之路：

把这道题和昨天的题一对比，我就发现了相似点和不同点。一个是所有可能一个是只要m个。再结合昨天的题，我发现了，所谓的多少个，就是数整个二叉树向右劈叉了几次，由此，我想到了在昨天的代码上就一个参数，判断他向右劈叉了多少次。

#include <iostream>
using namespace std;
int N,M;
void DFS(int n,int sta,int count){//sta是状态，将所选的数用二进制的1存着。
                                   //count就是记录劈叉次数
    if(n > N)return ;//当我们遍历超过了N，就需要停下来
    if(count == M){
        for(int i = 0;i < N;i ++)
            if(sta >> i & 1)
                cout << i+1 << " ";
        cout << endl;
        return ;
    }
    DFS(n+1,sta | 1 << n ,count +1);//向右才有需要的，所以count+1
    DFS(n+1,sta,count);//向左不需要变，继续去找

}
int main (){
    cin >> N >> M;
    DFS(0,0,0);
    return 0;
}

总结：一次通过，真开心，哈哈哈哈。