深度优先搜索的基础

给定整数a1,a2........an,判断是否可以从中选出若干数，使他们的和恰好为k

1<=n<=20

-1e8<=a1<=1e8

-1e8<=k<=1e8

输入

4

1 2 4 7

13

输出

Yes

输入

4

1 2 4 7

15

输出

No

这是个简单的深搜题，以前也做过几个深搜题，每次都是背模版做的从来没有理解过，这次，反倒简单的题目，自己仔仔细细的把递归的过程想了一遍，总算是通了，算然只是皮毛，但想通了，还是挺开心的

做深搜最怕的就是递归递不清楚

还是要画一下图吧，我觉得不画图的话很难想的清楚

附上代码

#include<cstdio>
using namespace std;
int a[10000];
int n,k;
bool dfs(int i,int sum)
{
    if(i==n) return sum ==k;
    if(dfs(i+1,sum)) return true;
    if(dfs(i+1,sum+a[i])) return true;
    return false;
}
int main ()
{
    int i;
    scanf("%d",&n);
    for( i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&k);

    if(dfs(0,0)) printf("Yes\n");
    else printf("No\n");
    return 0;
}