sum - An algorithm to determine a subset sequence in O(n)?

Question

How can i aproach this problem by induction?

Suppose that you are given an algorithm as a black box you cannot see how it is designed it has the following properties: if you input any sequence of real numbers and an integer k, the algorithm will answer YES or NO indicating whether there is a subset of numbers whose sum is exactly k. Show how to use this black box to find the subset of a given sequence {X1, …., Xn} whose sum is k. You can use the black box O(n) times.

Any idea?

Answer 1

I'm not entirely convinced that induction is necessary here.

Here's my two cents:

Suppose you have a sequence of numbers S, and integer k, and you already know that there exists a subset of numbers whose sum is k. Now, remove a number from your sequence (call it i), and use your black box on what remains (using the same k as before).

• If the algorithm returns YES on the new sequence, what does that tell you about i and any subset of S whose sum is k?
• If the algorithm returns NO on the new sequence, what does that tell you about i and any subset of S whose sum is k?