>>/105758/
> инвариант ломается, так сумма срванивается уже не с тем же k, как минимум
Это правда, но это не существенно. Пусть искомый алгоритм это функция F(a_1, a_2, ..., a_n; k) = {s_1, s_2, ..., s_n}, выдающая искомые подмассивы. Развернем ее по аргументу k и сделаем функцию F^(-1)(a_1, a_2, ..., a_n; s_1, ..., s_n) = k_max, которая выдает максимальную возможную k, при которой алгоритм генерирует заданные подмножества {s_1, ..., s_n}. Уравнение F^(-1)((a_1+c), (a_2+c), ..., (a_n+c); s_1, ..., s_n) = xk наверняка можно решить при любых c и k.
> он ничего не пропускает
То есть ты сначала двигаешь правую границу отрезка, затем левую? Это не решает проблему, в 2*N итераций ты не уложишься все равно, да и вообще в L*N такое, чтоб L была константой. Рассмотри например случай [1 2 3 4 5], k=6.