4
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ I don't think you need induction for this, you have basically paraphrased the proof already. Just write down the algorithm in pseudo code and prove that it finds such a subset if one exists and that it says "no subset sums to $k$" if none exists. You should probably shed more light on why the set you end up with isn't a strict superset of what you want; what I mean is, you should clarify why the resulting set doesn't include unnecessary elements. $\endgroup$ – G. Bach Sep 12 '13 at 1:19
  • $\begingroup$ Have you thought about a divide and conquer approach? There is probably no runtime difference with the black box, but for the general problem, there is. $\endgroup$ – Raphael Nov 11 '13 at 15:37
3
$\begingroup$

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\}$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.