Finding the subset of $S$ that sums up to $k$ using a black box in $O(n)$ time

Question

Suppose you are given an input set $S$ of $n$ numbers, and a black box that if given any sequence of real numbers and an integer $k$ instantly and correctly answers whether there is a subset of input sequence whose sum is exactly $k$. I want to show how to use the black box $O(n)$ times to find a subset of S that adds up to $k$.

This is what I've done: the first time we enter our set $S$. If it returns yes we can continue, otherwise it isn't possible to form the sequence which sums up to $k$. The next step is to test our set without the first element. If the black box returns yes we can delete it from our set otherwise we know that it is needed. We do this for each element and our $S$ shrinks to a set which sums up to $k$. Can I use induction to prove this?

Answer 1

Let $S = \{a_1,\ldots,a_n\}$, and denote $S^t$ the set after deciding the fate of $a_t$. If you want to use induction, here is your induction hypothesis:

1. If there is a subset of $S$ that sums to $k$, then there is a subset of $S^t$ that sums to $k$.
2. Every subset of $S$ that sums to $k$ includes $S^t \cap \{a_1,\ldots,a_t\}$.