例6.13 已知一個一維數(shù)組a[1..n](n<25)，又已知一整數(shù)m。 如能使數(shù)組a中任意幾個

/*
例6.13 已知一個一維數(shù)組a1..n，又已知一整數(shù)m。
如能使數(shù)組a中任意幾個元素之和等于m，則輸出YES，反之則為NO。
【分析】對于一個已確定的數(shù)組a[1..n]和一個確定的數(shù)m，
判斷能否使數(shù)組a中任意幾個元素之和等于m，
等價于判斷能否從數(shù)組a中取任意數(shù)使其和為m。
對于a中任意元素a[n]只有取與不取兩種情況：

(１)取a[n]：
則此時問題轉(zhuǎn)化為：對于一個已確定的數(shù)組a[1..n-1]和一個確定的數(shù)m-a[n]，
判斷能否使數(shù)組a[1..n-1]中任意幾個元素之和等于m-a[n]。

(２)不取a[n]：
則此時問題轉(zhuǎn)化為：對于一個已確定的數(shù)組a[1..n-1]和一個確定的數(shù)m，
判斷能否使數(shù)組a[1..n-1]中任意幾個元素之和等于m。

    若用函數(shù)sum(n,m)表示能否從數(shù)組a[1..n]中取任意數(shù)使其和為m，
    只要sum(n-1,m-a[n])和sum(n-1,m)當(dāng)中有一個值為真，

    則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傳遞結(jié)果
else if (n==1) return; //n=1作為遞歸邊界，不再遞歸下去
else //進(jìn)行兩種選擇
{
sum(n-1,m-a[n]);
sum(n-1,m);
}
}