Существует ли комбинация K целых чисел, чтобы их сумма была равна заданному числу?

Я вспотел над этим вопросом, на который меня попросили ответить (это технически домашнее задание). Я рассматривал хеш-таблицу, но я как бы застрял на точных деталях того, как я бы это сделал.

Вот вопрос:

Учитывая k наборы целых чисел A ₁ , A ₂ , .., A _k общего размера O ( n ), вам следует определить, существуют ли a ₁ ϵ A ₁ , a ₂ ϵ A ₂ , .. , a _k ϵ A _k , так что a ₁ + a ₂ + .. + a _{k -1} = a _k . Ваш алгоритм должен работать в T _k ( n ) время, где T _k ( n ) = O ( n ^{k / 2} × log n ) для четное k и O ( n ^{( k +1) / 2} ) для нечетных значений k .

Может ли кто-нибудь дать мне общее направление, чтобы я мог приблизиться к решению этой проблемы?