203021 - 平衡奶牛子集

我们定义一个奶牛集合 S 是平衡的，当且仅当满足以下两个条件： 1.S 非空。 2.S 可以被划分成两个集合 A 和 B，满足 A 里的奶牛产奶量之和等于 B 里的奶牛产奶量之和。划分的含义是：A ∪ B = S 且 A ∩ B = ∅。 现在给定大小为 n 的奶牛集合 S，询问它有多少个子集是平衡的。请注意，奶牛之间是互不相同的，但是它们的产奶量可能出现相同。

第一行一个整数 n（1≤n≤20），表示奶牛的数目。 第 2 至 n + 1 行，每行一个数 ai（1 ≤ ai ≤ 108），表示每头奶牛的产奶量。

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

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