Здравствуйте, virusmxa, Вы писали:

V>Опубликовал реализацию алгоритма на Java: https://github.com/virusmxa/things (git://github.com/virusmxa/things.git)

Ну... В таком виде он не нужен. Совсем и полностью. SubsetSumSolver, строки 48-56. Вопрос: раз уж вы динамику применяете, почему бы на ней все и не сделать? Ответ она тоже умеет строить, это несложно. Если усложнить, ей же можно и все ответы построить.

Кроме того, замечены:
* Совершенно ненужные наследования (BitVector, Combination, CombinationSequence, SubsetSizesSequence). Первый вообще не нужен, можно в BitMatrix нужные методы сделать. Длину можно там же хранить. Второй заменяется на обычный construction method. Остальные 2 зачем-то от AbstractCollection наследуются. Хотя достаточно было бы Iterable реализовать.
* Нарушения контрактов при наследовании (CombinationsSequence.iterator.next() — точно). Там же и еще в SubsetSizesSequence несогласован интерфейс size и размер iterable...
* Неоптимальный toString в BitVector

V> Требуется определить, какие операции в сумме дают некорректный остаток. После фильтрации операций по сумме (сумма каждой операции не должна превышать остаток) их осталось 97. Предложенный алгоритм нашёл 3 операции за 0.016 секунды.

А какого порядка там суммы были и с какой точностью? Если это порядка 10-ка тысяч рублей (и считать в копейках), та же динамика будет работать быстро (секунды). До сотен тысяч — пару минут. С учетом практичности данной задачи ее как раз стоит решать обычным динамическим программированием. Если не торопясь, за час вместе с прогоном и отладкой можно управиться. Ваш код писался явно гораздо дольше, его сложнее отлаживать (многопоточность) и при этом в качестве базы ту же динамику использует. Не окупаются затраты. Окупятся, только если subset sum problem решать десятками, сотнями и тысячами в один день. Может быть, при этом имело бы смысл параллелить динамику (она параллелится, но достаточно хитро и сложно), а не перебор.

P.S. CombinationsSequence.lg2(_sum) > 31 никогда не будет true, так как _sum — int.