題意做法: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存