AcWing 93 递归实现组合型枚举

发表于 更新于 分类于 ， 阅读次数： 本文字数： 115 阅读时长 ≈ 1 分钟

题目

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;

int n, m;// n个数

vector<int> chosen;

void calc(int x){
	//剪枝
	if ( (chosen.size() > m) || (chosen.size() + (n - x + 1) < m) )
		return;
	//边界输出
	if (x == n + 1) {
		for(auto i = 0; i < chosen.size(); ++i) {
			cout << chosen[i] << " ";
		}
		cout << '\n';
		return;
	}	
	/*字典序小的在前*/
	// 选择x-分支
	chosen.push_back(x); // 记录x已被选择
	calc(x + 1); // 递归求解子a问题
	chosen.pop_back(); // 回溯
	// 不选x-分支
	calc(x + 1);
}

int main(){
	cin >> n >> m;
	calc(1); 
}

Debug

字典序