Добрый день всем посетителям. Изучая вариации задачи о рюкзаке столкнулся с следующей, на первый взгляд очень простой, проблемой: Дан набор гирек массой m1, …, mN. Разделите этот набор на две кучки равной массы, содержащие равное число гирек(и выведите их).

Обычный рюкзак, но с дополнительным подсчетом числа гирь в каждом подходящем варианте подбора нужной массы, в дополнительной матрице(если половину общей массы мы можем собрать разным числом гирь, получив эти способы, берем один из тех, в которых число гирь равно половине от общего числа) не прошел. Видимо возможны такие входные данные, когда моя реализация не учитывает какой то необходимый вариант.

Мельком слышал, что эта задача решается динамикой d[i][j][k]:bool, где d[i][j][k] обозначает, можно ли используя первые i гирь получить кучку весом ровно j, в которой ровно k гирь. Только вот как именно реализовать эту динамику и даже получив ее, как по ней восстановить первую часть ответа я не знаю. Поэтому и обращаюсь к сообществу с этой проблемой, буду благодарен за идеи в решении и даже сами решения. (если вы все же решите написать вариант решения, опишите, пожалуйста, достаточно подробно все моменты, дабы у меня не возникали глупые и ненужные вопросы к вам)