部分和问题(入门题)（c++与c)（简单搜索）

部分和问题(入门题)

时间限制：1000 ms  |  内存限制：65535 KB 难度：0 描述

给你n个数(a1,a2,a3.......an) ,是否存在某一些数字加起来等于k,有就输出 "YES",否则输出 "NO"。

数据范围：n<20;

a1+a2+....an在int范围里面.

输入 多组输入每组第一行输入两个数n,k第二行输入n个数a1 a2 ...... an 输出 如果存在一些数加起来为k输出"YES";否则输出"NO". 样例输入 5 6 2 3 5 2 1 3 6 2 3 9 样例输出 YES

NO

用C++写；

#include<iostream> using namespace std; int n,k; int a[10009]; int gg(int i,int sum) {     if(sum>k)//剪枝         return 0;     if(i==n)         return sum==k?1:0;     if(gg(i+1,sum))//深搜 重点         return 1;     if(gg(i+1,sum+a[i]))         return 1;     return 0; } int main() {     while(cin>>n>>k)     {         int i;         for(i=0;i<n;i++)             cin>>a[i];         if(gg(0,0))             cout<<"YES"<<endl;         else            cout<<"NO"<<endl;     }     return 0; }

用C写； #include<stdio.h> int n,k; int a[10009]; int gg(int i,int sum) {     if(sum>k)         return 0;     if(i==n)         return sum==k?1:0;     if(gg(i+1,sum))         return 1;     if(gg(i+1,sum+a[i]))         return 1;     return 0; } int main() {     while(~scanf("%d%d",&n,&k))     {         int i;         for(i=0;i<n;i++)             scanf("%d",&a[i]);         if(gg(0,0))             printf("YES\n");         else             printf("NO\n");     }     return 0; } return 0;

      部分和问题

描述 给定整数a1、a2、.......an，判断是否可以从中选出若干数，使它们的和恰好为K。 输入 首先，n和k，n表示数的个数，k表示数的和。 接着一行n个数。 （1<=n<=20,保证不超int范围） 输出 如果和恰好可以为k，输出“YES”，并按输入顺序依次输出是由哪几个数的和组成，否则“NO” 样例输入 4 13 1 2 4 7 样例输出 YES 2 4 7 用C语言写； #include<stdio.h> #include<stack> #include<iostream> using namespace std; stack<int>s; int n,k,a[1000]; int gg(int i,int sum) {     if(sum>k)         return 0;     if(i==n)         return sum==k;     if(gg(i+1,sum))         return 1;     if(gg(i+1,sum+a[i]))     {         s.push(a[i]);         return 1;     }     return 0; } int main() {     int i;     while(~scanf("%d%d",&n,&k))     {         for(i=0;i<n;i++)         scanf("%d",&a[i]);         if(gg(0,0))         {             printf("YES\n");             int flag=1;             while(!s.empty())             {                 printf(flag==1?"%d":" %d",s.top());                 s.pop();                 flag=0;             }             printf("\n");         }         else             printf("NO\n");     }     return 0; }

用C++写；

#include<iostream> #include<stack> using namespace std; int n,k,a[100000]; stack<int>s; int gg(int i,int sum) { if(sum>k) return 0; if(i==n) return sum==k; if(gg(i+1,sum)) return 1; if(gg(i+1,sum+a[i])) { s.push(a[i]); return 1; } return 0; } int main() { int i; while(cin>>n>>k) { for(i=0; i<n; i++) cin>>a[i]; if(gg(0,0)) { cout<<"YES"<<endl; int flag=1; while(!s.empty()) { if(flag) cout<<s.top(); else cout<<" "<<s.top(); s.pop(); flag=0; } cout<<endl; } else cout<<"NO"<<endl; } return 0; }