题目描述：给定整数a1、a2、········、an，判断是否可以从中选出若干数，使他们的和恰好为k。

　　分别输入n，a[1~n]，k

　　若是存在若干数的和恰为k，则输出YES， 否则 输出NO

限制条件：

1、1<=n<=20

2、-108<=ai<=108

3、-108<=k<=108

样例1

输入：4

　　　1 2 4 7

         13

输出：YES

源代码：

/*看到这个问题首先会想到穷举的办法，欲得到k数，则在n个数中的每一个数都有选择的机会，也就是说时间复杂度为2的n次方

好大的复杂度，我的第一反应是放弃这种方法，但是注意到限制条件中，对于数据量的限制，最大是20，即为2的20次方，

快速的换算下就是16的5次方，最多就是10的6次方，也就是说这个方法是可行的。*/

#include <stdio.h>

int a[25];

int k;

int n; //将其设为全局变量便于使用

bool dfs(int i, int sum) //分别表示当前函数的序号和前i个中的若干数的和

{

    if(i == n + 1) return sum == k;

    ///if(sum == k) return true; //若是前i个数就存在，后面的数，不用考虑直接输出ture

    if(dfs(i + 1, sum + a[i])) return true;//判断当前数存在的情况

    if(dfs(i + 1, sum)) return true; //判断当前数不存在的情况

    return false; //该情况不成立的情况

}

int main ()

{

    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)

    {

        scanf("%d", &a[i]);

    }

    scanf("%d", &k);

    if(dfs(1, 0)) printf("YES\n");

    else printf("NO\n");

    return 0;

}

看起来这个更像是递归问题，而不是深搜问题。

当你理解这个程序流程后，会发现其实他是深搜。将一种情况走到底后，再次选择另一条路

。