子集和(Subset Sum)

题目描述

给定 $n$ 个数字 $a_1,a_2,\dots,a_n$ 构成一个集合（本题中所指的集合元素允许相等），请计算有多少子集的和大于 $0$？

输入格式

第一行，输入一个整数 $n$。

第二行，$n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

一个整数表示答案。

样例输入 #1

3
-1 -2 4

样例输出 #1

4

数据范围

【样例解释】

$4 > 0$, $4 - 1 > 0$, $4-2>0$, $4-2-1>0$。

【数据范围】

$50\%$ 的数据，$1\le n \le 20,-1000 \le a_i \le 1000$；

$100\%$ 的数据，$1\le n \le 40,-10^9 \le a_i \le 10^9$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1400。

测试点分布

出处：原题链接