Сумма-подмножество с фиксированным размером подмножества

Задача сумма-подмножество гласит:

Для данного набора целых чисел существует ли непустое подмножество, сумма которого равна нулю?

В целом эта проблема является NP-полной. Мне любопытно, известна ли сложность этого небольшого варианта:

Для данного набора целых чисел существует ли подмножество размера k , сумма которого равна нулю?

Например, если k = 1 , вы можете выполнить двоичный поиск, чтобы найти ответьте в формате O (log n) . Если k = 2 , то вы можете ge t это до O (n log n) (например, см. Найдите пару элементов из массива, сумма которых равна заданному числу ). Если k = 3 , то вы можете выполнить O (n ^ 2) (например, см. Поиск трех элементов в массиве, сумма которых наиболее близка к заданному числу ).

Есть ли известная граница, которую можно наложить на эту проблему как функцию k ?

В качестве мотивации я думал об этом вопросе Как разделить массив на 2 таких частей, что две части имеют одинаковое среднее значение? , и пытается определить, действительно ли оно является NP-полным. Ответ заключается в том, существует ли формула, описанная выше.

За исключением общего решения, мне было бы очень интересно узнать оптимальную оценку для k = 4 .