[Solved]: Output of well-known algorithms for the Subset sum problem

Problem Detail: 

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)

Asked By : Niels

Answered By : Juho

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33736

3.2K people like this

 Download Related Notes/Documents