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?
$\begingroup$
$\endgroup$
1
-
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$– JeffEAug 2, 2012 at 22:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
