Комбинаторная задача на сумму элементов множества

[B@R5uk]

Вот интересно, есть ли какой-нибудь способ быстро прикинуть сколько будет вариантов разбить заданное мультимножество (не обязательно последовательных чисел) на два с заданной суммой одной из половинок?

-- 03.02.2018, 22:40 --

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

[EtCetera]

B@R5uk в сообщении #1289945 писал(а):

Вот интересно, есть ли какой-нибудь способ быстро прикинуть сколько будет вариантов разбить заданное мультимножество (не обязательно последовательных чисел) на два с заданной суммой одной из половинок?

Это же что-то вроде задачи о сумме подмножеств (одной из разновидностей задачи о рюкзаке)?

[B@R5uk]

EtCetera в сообщении #1289954 писал(а):

Это же что-то вроде задачи о сумме подмножеств?

Да, именно её я и решаю сейчас. На компьютере разумеется. А эту тему создавал в связи с попыткой оценить трудоёмкость одного из подходов, который оказался совсем неудачным. Кстати, спасибо за ссылку. Там тоже есть описание каких-то алгоритмов.

[B@R5uk]

B@R5uk в сообщении #1289945 писал(а):

Заводим массив нулей размером, равным сумме элементов.

В первом элементе массива должна быть единица, разумеется. Иначе все элементы так нулями и останутся.