NYoj The partial sum problem(简单深搜+优化)

题目链接：http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=927

代码：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include <math.h>
 5 #include <algorithm>
 6 #include <iostream>
 7 using namespace std;
 8 
 9 int n,k;
10 int a[21];
11 int sum=0;
12 bool v[21];
13 
14 
15 int DFS(int sum,int m)
16 {
17     if(sum==k)
18     { 
19         return 1;
20     }
21     for(int j=m;j<n;j++)
22     {
23         v[j]=true;
24         if(DFS(sum+a[j],j+1)) return 1;//要深刻理解这个递归
25         v[j]=false;
26     }
27     return 0;
28 }
29 
30 int main()
31 {
32     while(~scanf("%d",&n)){
33         for(int i=0;i<n;i++){
34             scanf("%d",&a[i]);
35         }
36         scanf("%d",&k);
37         if(DFS(0,0))
38             printf("Of course,I can!
");
39         else
40             printf("Sorry,I can't!
");
41     }
42 }