对抗赛

题目描述:

程序设计对抗赛设有N（0≤50的整数）个价值互不相同的奖品，每个奖品的价值分别为S1，S2，S3……Sn（均为不超过100的正整数）。现将它们分给甲乙两队，为了使得甲乙两队得到相同价值的奖品，必须将这N个奖品分成总价值相等的两组。

编程要求：对给定N及N个奖品的价值，求出将这N个奖品分成价值相等的两组，共有多少种分法？

例如：N = 5，S1，S2，S3……Sn分别为1，3，5，8，9

则可分为{1，3，9}与{5，8}

仅有1种分法；

例如：N = 7，S1，S2，S3……Sn分别为1，2，3，4，5，6，7

有４种分法：

{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及S1，S2，S3……Sn。（每两个相邻的数据之间有一个空格隔开）。

输出格式:

一个整数，表示多少种分法的答案，数据若无解，则输出0。

样例输入:

(双击复制)

7
1 2 3 4 5 6 7

样例输出:

(双击复制)

4

时间限制: 1000ms
空间限制: 128MB

---