题意做法:DP
思路:
设f[i][j]表示前i个数能得到j的集合数(当然这里每一个结果都多算了一次,因为两个想等的结果的两个集合都算了,比如说前3个数,有{1,2}和{3}但是如果输入3的话,结果只能输出1.不过这没事,因为每个都多算了一次,最后的结果只要除2就行了),f[i][j](0<=j<=(i+1)*i/2)可以由f[i-1][k]得到
转移方程:
for i = 2 to n
f[i][i] =1;/*这选自己*/
j = i – 1;
for k = 0 to (j+1)*j/2 /*f[i][k] <----f[i-1][k] f[i][i+k] <-----f[i-1][k]*/
if(f[j][k] > 0)
f[i][k] += f[j][k];
f[i][k+i] += f[j][k];
最后还有一点就是N = 39时结果很大要用long long或者__int64存