问题描述

给出 n 件物品，每件物品有一个体积 $V\_i$，求从中取出若干件物品能够组成的不同的体积和有多少种可能。

输入格式

• 第 1 行 1 个正整数 $n$，表示物品的数量。
• 第 2 行 n 个正整数 $V_1, V_2, ..., V_n$，表示每个物品的体积。每两个数之间用一个空格隔开。

输出格式

• 输出一个整数，表示不同的体积和有多少种可能。

输入样例

3
1 3 4

输出样例

6

数据规模

• 对于 30% 的数据，满足：$n \leq 5$，$V\_i \leq 10$。
• 对于 60% 的数据，满足：$n \leq 10$，$V\_i \leq 20$。
• 对于 100% 的数据，满足：$n \leq 20$，$1 \leq V\_i \leq 50$。

解释

在输入样例中，给定 3 件物品，分别有体积 1、3 和 4。可以组成的不同体积和有：

• 选一个物品的情况：1，3，4。
• 选两个物品的情况：1 + 3 = 4，1 + 4 = 5，3 + 4 = 7。
• 选三个物品的情况：1 + 3 + 4 = 8。

因此，不同的体积和为：1，3，4，5，7，8，总共有 6 种可能。