2373: [C++一本通-动态规划]1.对抗赛

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:63 Solved:39

Description

程序设计对抗赛设有N(0<N<=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},仅有一种分法;

例如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,5}

{3,4,7}与{1,2,5,6}

{1,2,4,7}与{3,5,6}

有4种分法。

Input

N

S1,S2,S3,...,Sn.

Output

共有多少种分法,无解则输出0;

Sample Input Copy

7
1 2 3 4 5 6 7

Sample Output Copy

4

加入题单

算法标签: