Алгоритм определения последовательности подмножества в O (n)?

Question

Как я могу обратиться к этой проблеме по индукции?

Предположим, что вам предоставлен алгоритм как черный ящик, вы не можете видеть, как он создан, он обладает следующими свойствами: если вы вводите какую-либо последовательность действительных чисел и целое число k, алгоритм ответит ДА или НЕТ, указав, существует подмножество чисел, сумма которых точно равна k. Покажите, как использовать этот черный ящик, чтобы найти подмножество данной последовательности {X1, ...., Xn}, сумма которой равна k. Вы можете использовать черный ящик O (n) раз.

Есть идеи?

Answer 1

Я не совсем уверен, что здесь необходима индукция.

Вот мои два цента:

Предположит, у вас есть последовательность чисел S и целое k, и вы уже знаете, что существует подмножество чисел, сумма которых k. Теперь удалите номер из вашей последовательности (назовите его i) и используйте свой черный ящик на том, что осталось (используя тот же k, что и раньше).

• Если алгоритм возвращает YES на новой последовательности, что это говорит вам о i и любое подмножество S, сумма которых k?
• Если алгоритм возвращает NO на новую последовательность, что это говорит о i и любом подмножестве S, чья сумма составляет k?