Задача о сумме подмножеств

Задача о сумме подмножеств — это важная задача в теории сложности алгоритмов и криптографии.Задача заключается в нахождении (хотя бы одного) непустого подмножества некоторого набора чисел, чтобы сумма чисел этого подмножества равнялась нулю.Например, пусть задано множество {−7, −3, −2, 5, 8}, тогда подмножество {−3, −2, 5} даёт в сумме ноль.Задача является NP-полной. Эквивалентной является задача нахождения подмножества, сумма элементов которого равна некоторому заданному числу s.Задачу о сумме подмножеств также можно рассматривать как некоторый специальный случай задачи о ранце.Интересным случаем задачи о суммировании подмножеств является задача о разбиении, в которой s равна половине суммы всех элементов множества.