AcWing 递归实现组合型枚举 dfs
标签：size bsp 恢复 span turn img class return 递归
搜索顺序：
从前往后依次枚举每个位置放哪个数。同时保证每一个数都比前一个数大。
1 #include 2 using namespace std;
3 const int N = 30;
4 int n, m;
5 int way[N]; //方案
6 void dfs(int u, int start) { //u表示当前枚举到了哪个位置,start表示可以从哪个数枚举
7 if (u == m + 1) { //如果已经选好了m个数
8 for (int i = 1; i ) {
9 cout " ";
10 }
11 cout endl;
12 return;
13 }
14 //如果正在判断第u个位置，那么已经选了u-1个数
15 //从start到n一共有n-start+1个数
16 //如果把这么多个数都选上还凑不够m个数的话，就不合题意
17 //u-1+n-start+118 //化简即u+n-start19 if (u + n - start m) {
20 return;
21 }
22 for (int i = start; i //从start开始枚举
23 way[u] = i;
24 dfs(u + 1, i + 1);
25 way[u] = 0; //回溯恢复现场
26 }
27 }
28 int main() {
29 ios::sync_with_stdio(false);
30 cin.tie(0);
31 cout.tie(0);
32 cin >> n >> m;
33 dfs(1, 1); //从第一个位置开始枚举，可选择的数字最小是1
34 return 0;
35 }
AcWing 递归实现组合型枚举 dfs
标签：size bsp 恢复 span turn img class return 递归
原文地址：https://www.cnblogs.com/fx1998/p/12765758.html
评论