DFS

DFS

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止（属于盲目搜索）。

“一路走到头，不撞墙不回头”

深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

树状图图解

例如，想要从1到9，每到一个岔路口你有两种选择，你可以选择左枝，或者右枝，共两种可能，但是当你走到死胡同时，你只能原路返回，走到这个死胡同的上一个路口，走另一条路，依次类推，直到走到终点，也就是九。你可能会问，这不明摆着呢吗，直接从1经过8到9不就行了。没错，这是最直接的办法，但计算机傻啊，没有你聪明啊，它只会，一次一次的尝试，直到最终结果。

下面是图解

例题

给定整数a1、a2、…….an，判断是否可以从中选出若干数，使它们的和恰好为K。

输入

首先，n和k，n表示数的个数，k表示数的和。 接着一行n个数。 （1<=n<=20,保证不超int范围）

输出

如果和恰好可以为k，输出“YES”，否则“NO”

样例输入

4 13

1 2 4 7

样例输出

YES

思路

每一个数有加与不加两种可能，从树的一枝不加到尾，然后，再从叶末返回上一层叶节点，走另一个分支，也就是加上最后一个，与所求的和比较，不符再重复上述操作。直到找到与所求和相等返回Yes

实现

#include<iostream>
#include<stdio.h>
using namespace std;
int n,k,a[50];
int dfs(int i,int sum)
{
	if(i==n) 
		return sum==k;
	if(dfs(i+1,sum))
		return 1;
	if(dfs(i+1,sum+=a[i]))
		return 1; 
	return 0;
		
}
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>a[i];
	if(dfs(0,0))
		cout<<"YES"<<endl;
	else
		cout<<"No!"<<endl;
	return 0;	
}