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

$\endgroup$
  • 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 Dec 2 '14 at 19:18

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.