Вот интересно, есть ли какой-нибудь способ быстро прикинуть сколько будет вариантов разбить заданное мультимножество (не обязательно последовательных чисел) на два с заданной суммой одной из половинок?
-- 03.02.2018, 22:40 --Спросил и тут же придумал решение. Заводим массив нулей размером, равным сумме элементов. Дальше два цикла: во внешнем берётся элемент множества. Во втором цикле перебираются элементы массива начиная с последнего ненулевого элемента в сторону начала массива и содержимое каждой просмотренной ячейки добавляется к содержимому ячейки, сдвинутой вправо на величину элемента, взятого во внешнем цикле. Сложность
, где N — число элементов, а S — их сумма.