Задача 201: Подмножества с уникальной суммой
Для любого множества чисел A сумма (A) является суммой элементов A. Рассмотрим множество B = {1,3,6,8,10,11}. Существует 20 подмножеств B, содержащих три элемента, и их суммы:
сумма ({1,3,6}) = 10, сумма ({1,3,8}) = 12, сумма ({1,3,10}) = 14, сумма ({1,3,11}) = 15, сумма ({1,6,8}) = 15, сумма ({1,6,10}) = 17, сумма ({1,6,11}) = 18, сумма ({1,8,10} ) = 19, сумма ({1,8,11}) = 20, сумма ({1,10,11}) = 22, сумма ({3,6,8}) = 17, сумма ({3,6, 10}) = 19, сумма ({3,6,11}) = 20, сумма ({3,8,10}) = 21, сумма ({3,8,11}) = 22, сумма ({3, 10,11}) = 24, сумма ({6,8,10}) = 24, сумма ({6,8,11}) = 25, сумма ({6,10,11}) = 27, sum ({ 8,10,11}) = 29.
Некоторые из этих сумм встречаются несколько раз, другие уникальны. Для множества A пусть U (A, k) - множество единственных сумм k-элементных подмножеств A, в нашем примере мы найдем U (B, 3) = {10,12,14,18,21,25 , 27,29} и сумма (U (B, 3)) = 156.
Теперь рассмотрим 100-элементное множество S = {12, 22, ..., 1002}. S имеет 100891344545564193334812497256 50-элементные подмножества.
Определите сумму всех целых чисел, которые являются суммой ровно одного из 50-элементных подмножеств S, т. Е. Находят сумму (U (S, 50)).