algorithm - Using subset-sum oracle to determine which numbers are members of the subset

Question

I am having trouble starting off this particular homework problem. Here is the problem:

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.

I figure that the sequence should be sorted first, and anything < k should only be considered. Any help to get started would be greatly appreciated. Thanks.

Answer 1

Sorting is the wrong approach. Think about it this way: how can you use the oracle to determine whether a particular item in the set is part of the sum? Once you know whether that item is part of the sum, how can you use the oracle to figure out whether some other item is part of the sum?