从零开始学算法-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; }