題目描述

對于從1到N (1 <= N <= 39) 的連續(xù)整數(shù)集合，能劃分成兩個子集合，且保證每個集合的數(shù)字和是相等的。舉個例子，如果N=3，對于{1，2，3}能劃分成兩個子集合，每個子集合的所有數(shù)字和是相等的： {3} 和 {1,2} 這是唯一一種分法（交換集合位置被認(rèn)為是同一種劃分方案，因此不會增加劃分方案總數(shù)） 如果N=7，有四種方法能劃分集合{1，2，3，4，5，6，7}，每一種分法的子集合各數(shù)字和是相等的: {1,6,7} 和 {2,3,4,5} {注 1+6+7=2+3+4+5} {2,5,7} 和 {1,3,4,6} {3,4,7} 和 {1,2,5,6} {1,2,4,7} 和 {3,5,6} 給出N，你的程序應(yīng)該輸出劃分方案總數(shù)，如果不存在這樣的劃分方案，則輸出0。

思路

1.只有和為偶數(shù)時才有解 2.然后后面用dp f[i][j]表示前i個數(shù)和為j的個數(shù) f[i][j]=f[i-1][j]+f[i-1][j-i] 或=f[i-1][j] (加上的數(shù)大于總和) 最后輸出f[n][sum/2] O(n*sum)