[求助]这里有一道题的源码。大家看看,分析下算法思想。
任给 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
源码如下
long getsumcount(long data[],long count)
{ std::set<long> sumset;
int state[20] = {0};
long sum = 0,sp = 0;
while(sp>=0)
{ if(sp==count)
{ sumset.insert(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;
}
}
return (long)sumset.size();
}