思路分析

问题的转换

首先，我们可以把问题转化为一个经典的子集和问题。我们需要找到数组中所有的子序列，其元素和等于数组所有元素和的 $\frac{1}{2}$。因此，我们首先需要计算出数组的总和 $S$，然后检查是否存在某些子序列使得它们的和恰好是 $\frac{S}{2}$。

关键点

1. 总和为奇数时，显然不可能找到一个子序列的和恰好是 $\frac{S}{2}$，因为没有办法将一个奇数分成两个整数部分。

题目大意

给定一个大小为n的数组，请问存在多少种方案的子序列使得该子序列的和是原数组元素总和的一半。

样例输入

输入

4
1 2 3 4

输出

2

数据范围

$1 \le n \le 200$ 数组元素大于0且其总和不超过 $1e5$ , 保证方案总数不超过int的最大值。