patternModerate
Does Subset Sum allow multisets?
Viewed 0 times
allowdoessummultisetssubset
Problem
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?
Solution
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_i0 \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).
$$[-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_i0 \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).
Context
StackExchange Computer Science Q#3010, answer score: 10
Revisions (0)
No revisions yet.