/*
例6.13 已知一个一维数组a1..n，又已知一整数m。
如能使数组a中任意几个元素之和等于m，则输出YES，反之则为NO。
【分析】对于一个已确定的数组a[1..n]和一个确定的数m，
判断能否使数组a中任意几个元素之和等于m，
等价于判断能否从数组a中取任意数使其和为m。
对于a中任意元素a[n]只有取与不取两种情况：
(１)取a[n]：
则此时问题转化为：对于一个已确定的数组a[1..n-1]和一个确定的数m-a[n]，
判断能否使数组a[1..n-1]中任意几个元素之和等于m-a[n]。
(２)不取a[n]：
则此时问题转化为：对于一个已确定的数组a[1..n-1]和一个确定的数m，
判断能否使数组a[1..n-1]中任意几个元素之和等于m。
若用函数sum(n,m)表示能否从数组a[1..n]中取任意数使其和为m，
只要sum(n-1,m-a[n])和sum(n-1,m)当中有一个值为真，
则sum(n,m)为真，否则为假。因此，可以用递归来解此题。
递归终止条件为：
if (a[n]==m) sum=true;
else if (n==1) sum=false;采用全程变量编写程序如下：
*/
#include<iostream>
using namespace std;
const int max1=51;
int a[max1],n,m;
bool flag;
void sum(int ,int );
int main()
{
cin>>n;
for (int i=1; i<=n; ++i) cin>>a[i];
cin>>m;
flag=false;
sum(n,m);
if (flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;}
void sum(int n,int m)
{
if (a[n]==m) flag=true; //利用全局变量falg传递结果
else if (n==1) return; //n=1作为递归边界，不再递归下去
else //进行两种选择
{
sum(n-1,m-a[n]);
sum(n-1,m);
}
}
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
