2
$\begingroup$

According to Wikipedia:

In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero? For example, given the set {−7, −3, −2, 5, 8}, the answer is yes because the subset {−3, −2, 5} sums to zero. The problem is NP-complete.

What is the output of the known algorithms which resolve exactly the subset sum problem?

For example:

  • The algorithm which take $O(2^N*N)$ time.
  • The algorithme which take $O(2^{N/2})$ time.

Is it just Yes / No or do they also give the extraction of solution?

Example:

$A = \{1, 3, 4, 5\}$

$k = 8$ (The search item)

  • Output : YES
  • Output : {1,3,4}, {5,3} (where 1+3+4=8 and 5+3=8)
Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The question "is there a subset that sums up to $t$?" has a YES/NO answer. In general, we shouldn't expect an algorithm to do more than it is asked to, so to speak. However, it is rather common that when an algorithm answers YES, it can also naturally give you a certificate that proves it. Moreover, when this happens, you typically get a one valid solution. (This was just a clarification because your example outputs 2 valid solutions. Listing all solutions is a different thing).

Both algorithms you mention explicitly step through certain subsets, and so it is easy for them to also output the subset whose elements sum up to $t$. Whether you care about that extra information is up to you then.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Also, given an algorithm for the decision version of SUBSET-SUM, we can use it as a black box to solve the search version. $\endgroup$
    – Yuval Filmus
    Commented Dec 2, 2014 at 19:18
  • $\begingroup$ When you say "both algorithms" do you know which ones @csblo may be referring to? The top one I suppose it's just a brute force search e.g. the power set of all elements is $2^n@$ and a brute-force sum (or check) for each subset would be $N$, so we end up with $O(2^N N)$. But what about the algorithm that runs in $O(2^{N/2})$, do you know what algorithm he may be referring to? $\endgroup$
    – Josh
    Commented Apr 20, 2020 at 22:27
  • $\begingroup$ @YuvalFilmus Just reading your comment above, the runtime complexity of that solution using SUBSET-SUM as a black box can be very different for the decision problem right? $\endgroup$
    – Josh
    Commented Apr 20, 2020 at 22:30
  • 1
    $\begingroup$ @Josh The other one is probably the one due to Horowitz and Sahni - it's quite simple as well. $\endgroup$
    – Juho
    Commented Apr 21, 2020 at 4:26
  • 1
    $\begingroup$ @Josh Not really. It is at most a factor of $n$ slower, where $n$ is the number of elements. Given that algorithms for subset sum run in exponential time, it's not a big difference. $\endgroup$
    – Yuval Filmus
    Commented Apr 21, 2020 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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