Задачи
Сколько разных?
Сколько разных?
Для заданного множества n целых чисел a[1]
, . . ., a[n]
определить общее количество различных чисел, представляющих суммы элементов непустых подмножеств данного множества. Иными словами определить мощность множества сумм элементов всевозможных непустых подмножеств данного множества.
Входные данные
В первой строке задано число n. Во второй строке заданы числа a[1]
, ..., a[n]
(1 ≤ n ≤ 20, -10^5
≤ a[i]
≤ 10^5
).
Выходные данные
Вывести мощность множества сумм элементов.
Пример
Входные данные #1
1 99999
Выходные данные #1
1
Входные данные #2
3 2 4 6
Выходные данные #2
6