BFS笔记

Kinghero King of the summit 2023-10-14 15:56:24 0

#include <bits/stdc++.h> 
using namespace std;
// 从n个数中选k个数
int n,k;
int res[15];  // 答案数字
bool vis[15]; // 标记数组

// 函数作用:表示当前选的是第几个数
void dfs(int x){
	// 当前选的数超过k个,就结搜索,
	if(x>k){
		// 输出答案
		for(int i=1;i<=k;i++){
			cout<<res[i]<<" ";
		}
		cout<<endl;
		return;
	}
	// 从1~n个数中选
	for(int i=1;i<=n;i++){
		// 全排列:没有数字大小限制,只有一个条件:数字没被选过
		// if(vis[i] != 1){
		
		// 组合:数字没被选过 && 当前选的数字不能小于前一个数字
		if(vis[i] != 1 && res[x-1]<i){
			res[x] = i;  // 把这个数字记录下来
			vis[i] = 1;  // 标记这个数字,后面不能再选了
			dfs(x+1);
			vis[i] = 0;  // 回溯,后续的答案里面也可能有这个数字
		}
	}
}

int main(){
	cin>>n>>k;
	dfs(1);
	return 0; 
}
{{ vote && vote.total.up }}