Given a set of integers $S=\{s_1,s_2,...,s_n\}$ and a target number $T$, find a subset of $S$ that adds up exactly to $T$ in $O(nT)$ time.

I am not quite sure how to solve this but I think I have the workings of a start in progress.

If we say the last number we choose is $s_i$, then this reduces the problem to finding a subset of $S\backslash\{s_i\}$ that adds up to $T-s_i$.

I am having trouble coming up with a recurrence relationship for this because I am not sure how I would ensure the solution works. In other words, if there is a number $s_i$ that cannot be used in the subset that adds up to $T$, I am not sure how to express this.

I am thinking that the stopping conditions for the recurrence would be when all elements of $S$ are greater than $T$, in which case there is no solution, or when we find an element equal to $T$.

Could anyone point me in the right direction here and perhaps give more details about how to write a proper recurrence relationship for this problem?

  • 2
    $\begingroup$ See here: en.wikipedia.org/wiki/… $\endgroup$ – Yuval Filmus Nov 2 '15 at 7:59
  • 1
    $\begingroup$ 1) Try a specific recurrence, i.e. try to prove it correct using unduction. 2) Following your idea, anchors naturally occur when the set of allowed integers contains only one element and/or the target value is zero (assuming everything is positive here). $\endgroup$ – Raphael Nov 2 '15 at 8:33

Your Answer

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

Browse other questions tagged or ask your own question.