Задача 201
Подмножества с уникальной суммой

Пусть sum(A) - сумма элементов для любого множества чисел A.
Рассмотрим множество B = {1,3,6,8,10,11}.
Существует ровно 20 подмножеств B, которые состоят из трех элементов, а суммы этих подмножеств имеют следующие значения:

sum({1,3,6}) = 10,
sum({1,3,8}) = 12,
sum({1,3,10}) = 14,
sum({1,3,11}) = 15,
sum({1,6,8}) = 15,
sum({1,6,10}) = 17,
sum({1,6,11}) = 18,
sum({1,8,10}) = 19,
sum({1,8,11}) = 20,
sum({1,10,11}) = 22,
sum({3,6,8}) = 17,
sum({3,6,10}) = 19,
sum({3,6,11}) = 20,
sum({3,8,10}) = 21,
sum({3,8,11}) = 22,
sum({3,10,11}) = 24,
sum({6,8,10}) = 24,
sum({6,8,11}) = 25,
sum({6,10,11}) = 27,
sum({8,10,11}) = 29.

Некоторые из этих сумм встречаются более одного раза, другие - уникальны.
Пусть U(A,k) - множество уникальных сумм k-элементных подмножеств A. В нашем примере, U(B,3) = {10,12,14,18,21,25,27,29} а sum(U(B,3)) = 156.

Теперь, рассмотрим 100-элементное множество S = {1^(2), 2^(2), ... , 100^(2)}.
S содержит 100891344545564193334812497256 50-элементных подмножеств.

Определите сумму всех целых чисел, которые являются уникальными суммами 50-элементных подмножеств S. Другими словами, найдите sum(U(S,50)).

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net