Сумма мультимножества

Недавно искал алгоритм для расчета всех мультимножеств из заданного множества. Мультимножество удовлетворяет условию — сумма равна заданному числу. На самом деле нужно было перебрать все варианты периода времени от нескольких дней до недели, при условии, что весь период разбит на отрезки времени длиной в несколько часов (например 5,6, и 7).

Эти классы задач довольны известны: en.wikipedia.org/wiki/Subset_sum_problem ^[1]

Что и привело меня к этому алгоритму: mathoverflow.net/questions/9477 ^[2]

Далее были приключения с «адаптацией» этого алгоритма, после чего идея была заброшена. Простой генератор с использованием product(given_set,repeat=count_items) и условием на сумму оказался самым шустрым вариантом!

После нескольких недель вернулся к данной задаче и понял, что для эффективности первоначального алгоритма нужно использовать графы или деревья. Анализ сложности алгоритмов пока у меня нет.

В итоге вот что получилось на этих выходных: nbviewer.ipython.org/gist/denfromufa/61b3ed4e902fd9d11d6a ^[3]

Пока не хватает:
* обработки мусора, который скапливается в графе;
* ограничение на количество элементов в найденных мультимножествах.
* оптимизации по времени и памяти.

Но это уже гораздо лучше алгоритма по второй ссылке и моих недавних попыток.