输入:

n=4

a={1,2,4,7}

k=13

输出:

YES

输入:

n=4

a={1,2,4,7}

k=13

输出:

NO

 

选出若干数,使它们的和恰好为k

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 using namespace std;11 12 int a[55];13 int n,k;14 //已经从前i项得到了和sum,然后对于i项之后的进行分支15 bool dfs(int i,int sum)16 {17 //如果前n项都计算过了,则返回sum是否与k相等18 if(i==n) return sum==k;19 //不加a[i]的情况20 if(dfs(i+1,sum)) return true;21 //加上a[i]的情况22 if(dfs(i+1,sum+a[i])) return true;23 //无论是否加上a[i]都不能凑成k就返回false24 return false;25 }26 27 void solve()28 {29 if(dfs(0,0)) printf("YES\n");30 else printf("NO\n");31 }32 33 int main()34 {35 cin>>n;36 for(int i=0;i
              
               >a[i];38 }39 cin>>k;40 solve();41 }
              
             
            
           
          
         
        
       
      
     

 

 

 

<<挑战程序设计竞赛>>读后感