Задача 105
Суммы особых подмножеств: проверка

Пусть S(A) представляет собой сумму элементов множества А размером n. Будем называть это множество особым суммарным множеством, если для любых двух непустых и непересекающихся подмножеств B и C справедливо следующее:

  1. S(B) ≠ S(C); т.е. суммы элементов подмножеств не могут быть равными.
  2. Если B содержит больше элементов, чем C, то S(B) > S(C).

К примеру, {81, 88, 75, 42, 87, 84, 86, 65} не является особым суммарным множеством, поскольку 65 + 87 + 88 = 75 + 81 + 84. В свою очередь, {157, 150, 164, 119, 79, 159, 161, 139, 158} удовлетворяет обоим правилам для всех возможных комбинаций пар подмножеств и его S(A) = 1286.

В текстовом файле sets.txt (щелкнув правой кнопкой мыши, выберите 'Save Link/Target As...') размером 4KБ записана сотня множеств, содержащих от семи до двенадцати элементов (два примера, рассмотренные выше, являются первыми двумя множествами в файле). Найдите все особые суммарные множества A1, A2, ..., Ak и найдите значение S(A1) + S(A2) + ... + S(Ak).

Примечание: Данная задача имеет также отношение к задачам №103 и №106.

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