[数据结构与算法]DFS——深度优先搜索

DFS

搜索的一个手段，从某个状态开始，不断的转移状态到无法转移，然后回退到前一步的状态，继续转移其他状态，如此不断重复，直至找到最终的解。

例题

给定整数a1，a2…an，判断是否可以从中选出若干数，使他们的和恰好为k。
条件：
1.1<=n<=20
2.-1e8<=ai<=1e8
3.-1e8<=k<=1e8

输入样例

4
1 2 4 7
13

输出样例

YES

输入样例

4
1 2 4 7
15

输出样例

NO

分析

显然我们可以用到dfs，从ai开始按顺序决定每个数加或不加，在全部n个数都决定后在判断它们的和是否等于k即可。
类似于树，
下面是代码

#include<bits/stdc++.h>
#include<algorithm>
#include<map>
#define ll long long
using namespace std;
const int N = 1e6+5;
int num[N]; 
int n, k;//定义全局变量，方便函数比较
bool dfs(int i, int sum){
	if(i==n){
		return sum==k;//如果已经有前n项和加了，那么返回sum是否与k相等
	}
	if(dfs(i+1,sum)){//不加上ai的情况
		return true;
	}
	if(dfs(i+1, sum+num[i])){//加上ai的情况
		return true;
	}
	//无论是否加上ai都不能得到sum==k，那么返回false
	return false;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		memset(num,0,sizeof(num));
		cin>>n;
		for(int i = 0;i < n;i++){
			cin>>num[i];
		}
		cin>>k;
		if(dfs(0,0)){
			cout<<"YES"<<endl;
		} 
		else{
			cout<<"NO"<<endl;
		}
	}
	return 0;
}

我自己加了多组输入输出，以方便验证。建议自己多调试几遍，以便自己理解。深搜就是从最开始的状态出发，便林所有可能的情况，由此对所有状况进行操作或列举出所有状态。
有个深搜例题，PojNo.2386传送门