Finding the subset of $S$ that sums up to $k$ using a black box in $O(n)$ time
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:


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