AcWing 93. 递归实现组合型枚举

前言

今天晚上还有三个小时，写一晚上简单题。划水。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
void dfs(int u,int sum,int state){if(sum+n-u<m){return;//sum 表示当前选了 sum 个数字，假设把所有的数字都选了都不足 m 个数字}//就说明选不了这么多个数字if(sum==m){for(int i=0;i<n;i++){if(state>>i&1){cout<<i+1<<" ";}}cout<<endl;return;}dfs(u+1,sum+1,state|1<<u);dfs(u+1,sum,state);
}
int main(){cin>>n>>m;dfs(0,0,0);return 0;
}

思路

比之前的那个题多了一个限制，之前是需要完整地选 n 个数字，现在是选择 m 个数字，所以判断一下，不能满足条件就不选了。AcWing 94. 递归实现排列型枚举。我觉得别人把这个二进制状态压缩写得贼熟练就是因为理解原理之后经常写，或者就是直接记住了。