4416 - Balanced Cow Subsets

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

• S 非空。
• S 可以被划分成两个集合 A,B，满足 A 里的奶牛产奶量之和等于 B 里的奶牛产奶量之和。划分的含义是，A\cup B=S 且 A\cap B=\varnothing。

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

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

第 2 至 n+1 行，每行一个数 a_i，表示每头奶牛的产奶量。

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

共存在三种方案。集合 {1,2,3} 可以划分为 {1,2} 与 {3}；集合 {1,3,4} 可以划分为 {1,3} 与 {4}；集合 {1,2,3,4} 可以划分为 {1,4} 与 {2,3}，共 3 种子集。

对于全部数据，保证 1\le n\le 20，1\le a_i\le 10^8。

USACO