1317：【例5.2】组合的输出

本题需要在n个元素总抽取r个元素，并输出这r个元素的所有组合，在这里我们使用dfs+回溯的算法进行求解，在dfs中我们首先枚举所有方案，然后看是否需要标记，对于这道题来说，不能重复搜索，所以我们需要判断标记并且标记没有被搜过的数字，然后进入下一层进行搜索，那么我们是否需要回溯呢，答案是需要的，例如 1 2 3 和 3 4 5，我们是需要回溯的

#include <bits/stdc++.h>

using namespace std;
int n,m;
int cnt[110];
bool vis[110];


void dfs(int start,int depth) {
	//终止
	if (depth > m) {
		for (int i = 1; i < depth; i++) {
			printf("%3d", cnt[i]);
		}printf("\n");
		return;
	}

	//枚举所有方案
	for (int i = start; i <= n;i++) {
		//查看标记-防止重复搜索
		if (!vis[i])
		{
			//搜索当前层
			cnt[depth] = i;
			//标记
			vis[i] = 1;
			//搜索下一层
			dfs(i + 1,depth + 1);
			//回溯
			vis[i] = 0;
		}
	}
}



int main() {
	
	cin >> n>>m;
	dfs(1,1);

	return 0;

}

在搜索与回溯中，我们可以进行重复性剪枝，因为题目所有要求的答案都是按照字典序进行排列的，所以我们每一次搜索都可以在上一次搜索的后面进行搜索，也就是在上一次方案的后面进行搜索。