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

Question

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

Вот вопрос:

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

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

Answer 1

Разделите наборы k на две группы. Для четного k обе группы имеют k / 2 множества в каждой. Для нечетного k одна группа имеет (k + 1) / 2, а другая имеет (k-1) / 2 набора. Вычислить все возможные суммы (взяв один элемент из каждого набора) в каждой группе. Для четного k вы получите два массива, каждый с n ^{k / 2} элементами. Для нечетного k один массив имеет n ^{(k + 1) / 2} , а другой массив имеет n ^{(k-1) / 2} элементов. Задача сводится к стандартному: «Учитывая два массива, проверьте, можно ли достичь указанной суммы, взяв один элемент из каждого массива».