8
$\begingroup$

In the Subset Sum problem can some of the given numbers $a_1,a_2,a_3,\dots,a_n$ be the same? For example, we might have $[1,1,1,2,3,4]$ and the target is $5$? Can I assume that I have a specific solution with numbers $2$ and $3$ and $1,1,1$ and $2$ is not?

$\endgroup$

migrated from cstheory.stackexchange.com Aug 2 '12 at 22:51

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 6
    $\begingroup$ You say potayto, I say potahto. It's quite common for computer scientists to blur the formal distinction between sets and multisets; the only way to be sure is to read the definition carefully. All variants of the Subset Sum problem are NP-complete. $\endgroup$ – JeffE Aug 2 '12 at 22:01
9
$\begingroup$

One question we could ask is "Can we reduce this back to the subset sum problem?" In this case, the answer is yes: for each duplicate $z$ we replace it with two numbers $x$ and $y$ such that $x+y=z$. $$[-1,-1,2,3]\to [-7,-1,2,3,6]$$

However, we need to be careful that we don't introduce additional solutions (those using just $x$ without $y$), which we can do by making $x>\lvert \Sigma(a_i)\rvert$ for $a_i<0\in A$, and $y<-\lvert\Sigma(a_i)\rvert$ for $a_i>0 \in A$. Specifically, this precludes the use of $x$ without $y$ (and vice versa) by making the sum of $x$ and all negative numbers strictly above zero (and thus doesn't satisfy the traditional subset sum problem).

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