Есть ли способ генерироватьвсе подмножества сумм s1, с2, ..., сk которые попадают в диапазон [A, B] быстрее, чем O ((k + N) * 2N / 2), где k - количество сумм в [A, B]? Обратите внимание, что k известно только после того, как мы перечислили все суммы подмножеств в [A, B].

Я сейчас использую модифицированныйГоровиц-Sahni алгоритм. Например, я сначала называю это для наименьшей суммы, большей или равной A, давая мне s1, Затем я называю это снова для следующей наименьшей суммы, большей чем s1, давая мне с2, Повторите это, пока мы не найдем сумму ск + 1 больше, чем B. Существует много вычислений, повторяемых между каждой итерацией, даже без восстановления начальных двух 2N / 2 списки, так есть ли способ сделать лучше?

В моей задаче N около 15, а величина чисел порядка нескольких миллионов, поэтому я не рассматривал маршрут динамического программирования.