二、任给 1<=n<=20 个不同的非零正整数，每个正整数最多使用1次，请问这n个正整数能够加和的结果共有多少种(不考虑和超出long的最大值的可以),
程序中请实现如下函数。用于计算数组data,中ncount的加和的数量。
long getsumcount(long data[], long count);
程序中可以出现别的辅助函数。或辅助结构等。

例如，
data[] = {1,2,3,4};
ncount = 4;
函数返回 10

分解如下。（0不算）

1  = 1
2  = 2
3  = 3 = 1+2
4  = 4 = 1+3

5  = 2+3 = 1+4
6  = 2+4 = 1+2+3
7  = 3+4 = 1+2+4
8  = 1+3+4
9  = 2+3+4
10 = 1+2+3+4
如上。所以结果是10种可能。
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <time.h>
#define libsize (1<<16)
#define hashsize (1<<16)
#define hashmask (0xffff)

using namespace std;

typedef struct node{
    long data;
    struct node *next;
}NODE;
NODE hashtab[hashsize];

const long MAX = 20;

bool IsNew(long array[], long len, long data);
void solve(const long data[], bool lib[], long a[], long len, long pos, long max, long num);
long _getsumcount(const long data[], long count);
long Sum(const long a[], int len);
long getsumcount(const long data[], long count);

int main(void)
{
      time_t startTime;
 time_t endTime;
 time(&startTime);
      long data[MAX]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

      for (long i=0; i<MAX; i++) //给数组赋值为1-100的随机数
      {
            long temp = rand()%100 + 1;
            if (IsNew(data, i, temp))
                  data[i] = temp;
      }

      for (long i=0; i<MAX; i++)
            cout << data[i] << ' ';
      cout << endl;

      int sum = 0;
      for (long i=1; i<=MAX; i++)
      {
            long s1 = getsumcount(data, i);
            long s2 = _getsumcount(data, i);
           
            cout << i << ": s1=" << s1 <<"  s2=" << s2 << endl;
            if (s1 == s2)
                  sum++;
      }
      cout << sum << endl;

      time(&endTime);
 cout << "time:" << difftime(endTime, startTime) << endl;

 getchar();
 return 0;
}
//////////////////////////////////////////////////////////////////////////
/*
  Author: goal00001111
*/
bool IsNew(long array[], long len, long data)
{
      for(int i=0; i<=len; i++)
            if (array[i] == data)
                  return false;
      return true;
}

long _getsumcount(const long data[], long count)
{
      bool lib[libsize];
      for (long i=0; i<libsize; i++)
            lib[i] = false;
      long *a = new long[count];

      for (int k=0; k<count; k++)
            solve(data, lib, a, count, 0, k, 0);

      delete []a;
      long sum = 1;
      for (long i=0; i<libsize; i++)
      {
            if (lib[i])
            {
                  sum++;
                // cout << i << ' ';
            }
      }
      return sum;
}

void solve(const long data[], bool lib[], long a[], long len, long pos, long max, long num)
{
      if (num == max)
      {
            for (int i=pos; i<len; i++)
            {
                  a[num] = data[i];
                  lib[Sum(a, num)] = true;
            }
      }
      else  //如果不是最后一个数字
      {
            for (int i=pos; i<len; i++)
            {
                  a[num] = data[i];
   solve(data, lib, a, len, i+1, max, num+1); //分析下一个数
            }
      }
}

long Sum(const long a[], int len)
{
      long sum = 0;
      for (int i=0; i<=len; i++)
            sum += a[i];
      return sum;
}
///////////////////////////////////////////////////////////////////////
/*
  Author: eastcowboy
*/

/*寻找并插入，找到而未插入返回0，未找到而插入返回1*/
static int hashinsert(long sum)
{
    NODE *p,*q;
    p = hashtab+ (sum & hashmask);
    while( p && (p->data!=sum) )
    {   q = p;
        p = p->next;
    }
    if( p )
        return 0;
    q->next = p = (NODE*)malloc(sizeof(NODE));
    p ->next = NULL;
    p ->data = sum;
    return 1;
}
/*删除hash表的第index条目*/
static void hashdelete(long index)
{   NODE *p,*q;
    p = hashtab[index].next;
    while(p)
    {   q = p;
        p = p->next;
        free(q);
    }
}
/*这才是正主^^*/
long getsumcount(const long data[],long count)
{
    long i;
    int state[MAX] = {0};
    long sum = 0,sp = 0;
    int ret = 1; /*由于0已经先放入表中，所以首先就有一个*/

    /*hash表初始化*/
    for(i=0;i<hashsize;++i)
    {   hashtab[i].data = 0;
        hashtab[i].next = NULL;
    }
    /*回溯求解*/
    while(sp>=0)
    {   if(sp==count)
        {   ret += hashinsert(sum);
            --sp;
        }
        switch( state[sp] )
        {   case 0:
                state[sp] = 1;
                sum += data[sp];
                ++sp;
                break;
            case 1:
                state[sp] = 2;
                sum -= data[sp];
                ++sp;
                break;
            case 2:
                state[sp] = 0;
                --sp;
                break;
        }
    }
    /*hash表销毁*/
    for(i=0;i<hashsize;++i)
    {   hashdelete(i);
    }
    return ret;
}