数组中，是否有 和值 为某值

求一个数组中，是否有 和值 为某值
怎样快速判断一个数组中，和值（任意1个或几个的和） 是否 等于某值：

例：

有数组： int v[10]={1,2,3,4,5,6,7,8,9,10};//数组值任意

是否存在：v[0] + v[2] + ... + v[9]=35; //数组中任意几个的和是否存在和值为35。

存在输出这几个数，不存在输出其他标记。



[解决办法]
编程难道以后很多这些问题么？（那我悲剧了！！！伤不起！）

先排序，再累加，再移动？神马算法还没学过，想着就头疼
[解决办法]
DP问题，参考编程之美。

bool dp[n][sum]表示n个数是否能组成和为sum.
[解决办法]
最简单的想法就是用穷举法
[解决办法]

C/C++ code

#include <iostream>using namespace std;bool isSum(int num, int *v, int length){    int *mark = new int[length+1];    int i, sum;    for(i = 0; i < length; ++i)        if(num == v[i])        {            cout<<v[i]<<endl;            delete[] mark;            return true;        }    for(i = 0; i < length+1; ++i)        mark[i] = 0;    while(mark[length] == 0)    {        ++mark[0];        for(i = 0; i < length; ++i)        {            if(mark[i] >= 2)            {                mark[i] -= 2;                ++mark[i+1];            }        }        sum = 0;        for(i = 0; i < length; ++i)        {            sum += mark[i] * v[i];        }        if(sum == num)        {            for(i = 0; i < length; ++i)                if(mark[i] != 0)                    cout<<"  "<<v[i];            cout<<endl;            delete[] mark;            return true;        }    }    delete[] mark;    return false;}int main(){    int v[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};    int num = 25;    //cin>>num;    if(!isSum(num, v, 10))        cout<<"不存在和值为"<<num<<endl;    return 0;}
[解决办法]
探讨

最简单的想法就是用穷举法

[解决办法]
因为和仅为35，可以用01背包来解，具体搜索 背包9讲
[解决办法]
int cnt;
void printa(int a[], int used[], int n)
{
   ++cnt;
   for (int i = 0; i < n; ++i)
   {
       if (used[i])
           cout<< a[i] << " ";
   }
   cout << endl;
}

void tt(int a[], int n, int sum, int used[], int i)
{
   if (i >= n)
       return;
  
   used[i] = 1;
   if ( sum == a[i] )
       printa(a, used, n);
   else
       tt(a, n, sum-a[i], used, i+1);
  
   used[i] = 0;
   tt(a, n, sum, used, i+1);
}

void main()
{
   int a[] = {1,2,3,5,6,7,8,9,10};
   const int n = sizeof(a)/sizeof(a[0]);

   int used[n] = {0};

   tt(a, n, 40, used, 0);

   if (0 == cnt)
       cout << "impossibility\n";
}
[解决办法]
C/C++ code
void isArrSomeElementsSumIs(int arr[], int cnt, int total, int start, int point){    // swap arr[start] arr[point]    int temp = arr[start];    arr[start] = arr[point];    arr[point] = temp;        if (temp == total)     {        for (int j = 0; j < point; j++)         {            cout << arr[j] << " ";        }        cout << temp << endl;    }     else     {        for (int i = start + 1; i < cnt; i++)         {            isArrSomeElementsSumIs(arr, cnt, total - temp, i, point + 1);        }    }        arr[point] = arr[start];    arr[start] = temp;    }void testIsArrSomeElementsSumIs(){    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};    isArrSomeElementsSumIs(arr, sizeof(arr) / sizeof(arr[0]), 35, 0, 0);}