NYOJ-927-The partial sum problem

时间限制： 1000 ms  |  内存限制： 65535 KB 难度： 2 描述 One day,Tom’s girlfriend give him an array A which contains N integers and asked him:Can you choose some integers from the N integers and the sum of them is equal to K.  输入 There are multiple test cases. Each test case contains three lines.The first line is an integer N(1≤N≤20),represents the array contains N integers. The second line contains N integers,the ith integer represents A[i](-10^8≤A[i]≤10^8).The third line contains an integer K(-10^8≤K≤10^8). 输出 If Tom can choose some integers from the array and their them is K,printf ”Of course,I can!”; other printf ”Sorry,I can’t!”. 样例输入 4 1 2 4 7 13 4 1 2 4 7 15 样例输出 Of course,I can! Sorry,I can't! #include <stdio.h>int flag;int result;int a[25];void fun(int x,int ans,int end){ if(ans==result) { flag=0; printf("Of course,I can!\n"); return ; } if(ans>result||x==end||flag==0) //剪枝，不然会超时 return ; for(int i=x;i<end;i++) { if(flag==0) break; ans += a[i]; fun(i+1,ans,end); ans -= a[i]; }}int main(){ int n,b; while(scanf("%d",&n)!=EOF) { flag=1; for(int i=0;i<n;i++) { scanf("%d",&a[i]); } scanf("%d",&result); fun(0,0,n); if(flag) { printf("Sorry,I can't!\n"); } } return 0;}