#1055. 「USACO 2012 Open Gold」Balanced Cow Subsets

我们定义一个奶牛集合 是平衡的，当且仅当满足以下两个条件：

• 非空。
• 可以被划分成两个集合 ，满足 里的奶牛产奶量之和等于 里的奶牛产奶量之和。划分的含义是， 且 。

现在给定大小为 的奶牛集合 ，询问它有多少个子集是平衡的。请注意，奶牛之间是互不相同的，但是它们的产奶量可能出现相同。

第一行一个整数 ，表示奶牛的数目。

第 至 行，每行一个数 ，表示每头奶牛的产奶量。

输出一个数表示方案总数。

样例解释

共存在三种方案。集合 可以划分为 与 ；集合 可以划分为 与 ；集合 可以划分为 与 ，共 种子集。

输入 #1

4 
1 
2 
3 
4

输出 #1

3

对于全部数据，保证 ，。