NYOJ The partial sum problem_综合

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!”.

样例输入

样例输出

Of course,I can!
Sorry,I can't!

     
      
       #include<cstdio>
      
      
       02.
       #include<cstdlib>
      
      
       03.
       #include<cstring>
      
      
       04.
       using namespace std;
      
      
       05.
       long long a[30],n,k,ok,s;
      
      
       06.
       void    DFS(int x){
          
      
      
       07.
       if(ok==0){
          
      
      
       08.
       if(s==k){
          
      
      
       09.
       printf("Of course,I can!\n");
      
      
       10.
       ok=1;}
      
      
       11.
       }
      
      
       12.
       if(x==n)return ;
      
      
       13.
       for(int i=x;i<n;++i){
          
      
      
       14.
       if((s+a[i])<=k){
          
      
      
       15.
       s+=a[i];
      
      
       16.
       DFS(i+1);
      
      
       17.
       s-=a[i];
      
      
       18.
       }
      
      
       19.
       }
      
      
       20.
       }
      
      
       21.
       int main()
      
      
       22.
       {
          
      
      
       23.
       long long i,j;
      
      
       24.
       while(scanf("%lld",&n)!=EOF){
          
      
      
       25.
       for(i=0;i<n;++i)
      
      
       26.
       scanf("%lld",&a[i]);
      
      
       27.
       scanf("%lld",&k);
      
      
       28.
       ok=0;s=0;
      
      
       29.
       DFS(0);
      
      
       30.
       if(ok==0)
      
      
       31.
       printf("Sorry,I can't!\n");
      
      
       32.
       }
      
      
       33.
       return 0;
      
      
       34.
       }