P14074

Balanced Cow Subsets

难度 4 级 小学 算法入门 双向搜索
讨论 统计 2通过 3提交 66.7%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

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

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

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

输入

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

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

输出

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

样例

样例 1
输入
4 
1 
2 
3 
4
输出
3

提示

共存在三种方案。集合 {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。

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交