ну такая граница точно левая, это же не хуже умножения матриц

мне вообще это нужно для ускорения брутфорса для решения задачи: дан набор положительных целых чисел {s1, s2, ..., sn}. Их сумма S. Также дано три положительных целых числа S1, S2, S3: S1 + S2 + S3 = S. Я могу выписать все наборы si (построить trie частичных сумм, к примеру и выписать все решения), суммирующиеся, допустим, в S1 и S3 (не важно — любые два) и решить для этих наборов задачу из вопроса выше. В данный момент это очень дорого по времени получается. Размерности невелики (n ~= 20)

смешно, что какую-то странную связь с 3SUM вы уже указали :)

угу)

только это не сама 3SUM, а всё намного печальнее) к сожалению

у 3SUM кажется сложность строго выше (а может быть и не строго), чем у этого алгоритма

Это проекция, только не про сумму подмножества, а про мультирюкзак

это multiple subset sum problem вообще

частный случай мультирюкзака

3SUM ограничивает возможную декомпозицию для subset sum при разбиении инпута на группы

на группы по 2-3?

а нельзя просто выписать эти битовые векторы, выписать минус эти битовые векторы и вызывать 3sum?

для 3sum fft алгос есть

На 2 группы стандартное решение 2^(N/2) и большее число групп его не улучшает

типа mitm

нет нельзя, забейте..

перенос существует, внезапно

в общем, эти схемы не работают и никто не знает, почему

в k-sum прямо чудесное (2^(N/k))^(k/2) = 2^(N/2) получается

единичную subset sum конструктивно я умею решать (относительно) быстро. Т.е. могу найти какое-то одно решение за O(S) памяти и (кажется) за O(n*S) времени