<p>Your (self) answer is ok, but you can also build a reduction in which there is no &quot;trivial&quot; solution.</p>
<p>Start from <span class="math-container">$X = \{ x_{1}, \ldots, x_{n} \}, x_i &gt; 0$</span> with target sum <span class="math-container">$K$</span> and build:</p>
<p><span class="math-container">$X' = \{  8 * x_{1}, \ldots, 8 * x_{n} \} \cup \{ 1, 1, 2 \}$</span> and target sum <span class="math-container">$K' = 8*K + 2$</span></p>
<p>In this case in order to solve the new problem <span class="math-container">$\langle X', K' \rangle$</span> you are &quot;forced to solve&quot; the original one, and there are at least two solutions to <span class="math-container">$\langle X', K' \rangle$</span> if there is a solution to <span class="math-container">$\langle X, K \rangle$</span>.</p>

CC BY-SA 4.0
2021-01-08T16:39:10.510Z
It seems to me like you should use $ \{ 1, 1 \} $ and $ K' = 8 * K + 2 $ so that if there is a solution to the original problem, it becomes two in the new one. In this formulation, it looks to me like there is the same number of solutions and you have to pick $ 2 $ every time.
user73236
CC BY-SA 4.0
2021-01-08T17:05:07.503Z
Sorry, I meant $ K' = 8 * K + 1 $.
user73236
CC BY-SA 4.0
2021-01-08T17:52:17.907Z
@user73236 in your version there is no distinction between the two $1$s so the solution counts as one. And also in my answer an original solution $Y$ becomes two: $Y \cup \{1,1\}$ and $Y \cup \{2\}$
Marzio De Biasi
CC BY-SA 4.0
2021-01-08T15:59:34.243Z
2021-01-08T15:59:34.243Z
Marzio De Biasi
<p>Yes, this appears to be true in the case that the integers are all positive. We simply take a Subset Sum instance defined by the set <span class="math-container">$ X = \{ x_{1}, \ldots, x_{n} \} $</span> and the target value <span class="math-container">$ K $</span> and create the set <span class="math-container">$ X' = X + \{ K \} $</span>. Then there are at least two solutions to this problem if there is at least one to the original. Likewise, if there are two solutions given to this At Least Two Subset Sum problem; we simply pick either of them unless one of them is <span class="math-container">$ \{ K \} $</span>, in which case we simply pick the other solution. Any solution to the At Least Two Subset Sum problem besides <span class="math-container">$ \{ K \} $</span> cannot have <span class="math-container">$ \{ K \} $</span> as a subset since <span class="math-container">$ K + \sum_{ s \in S } s &gt; K $</span> because all <span class="math-container">$ s $</span> are positive. So the other solution must solve the original problem.</p>

CC BY-SA 4.0
2021-01-08T08:55:37.033Z
2021-01-08T08:55:37.033Z
user73236
<p>I was wondering if there are any results that say how hard it is to answer the question are there TWO subsets that sum to a fixed value? In other words, the subset sum problem but asking if there are at least two or more solutions.</p>
<p>My thought is that potentially it is FNP, because the Another Solution Problem (ASP) for Subset Sum appears to be FNP (by reduction from 3SAT), but ASP assumes that at least one solution was already found. Is there a way to say something about the hardness of finding two solutions without prefacing that one was already found?</p>

<np-hardness><counting-complexity><reductions>
Knowing if there are two solutions to the subset sum problem
user73236
# Knowing if there are two solutions to the subset sum problem

(Asked by: username_0 on 2021-01-08)

I was wondering if there are any results that say how hard it is to answer the question are there TWO subsets that sum to a fixed value? In other words, the subset sum problem but asking if there are at least two or more solutions.

My thought is that potentially it is FNP, because the Another Solution Problem (ASP) for Subset Sum appears to be FNP (by reduction from 3SAT), but ASP assumes that at least one solution was already found. Is there a way to say something about the hardness of finding two solutions without prefacing that one was already found?

**Tags:** np-hardness, counting-complexity, reductions


---

## 2 answers

### Answer by username_1 on 2021-01-08. Score: 2

Your (self) answer is ok, but you can also build a reduction in which there is no "trivial" solution.

Start from $X = \{ x\_{1}, \ldots, x\_{n} \}, x\_i > 0$ with target sum $K$ and build:

$X' = \{ 8 \* x\_{1}, \ldots, 8 \* x\_{n} \} \cup \{ 1, 1, 2 \}$ and target sum $K' = 8\*K + 2$

In this case in order to solve the new problem $\langle X', K' \rangle$ you are "forced to solve" the original one, and there are at least two solutions to $\langle X', K' \rangle$ if there is a solution to $\langle X, K \rangle$.

> **Comments:**
> **username_0**: It seems to me like you should use $ \{ 1, 1 \} $ and $ K' = 8 * K + 2 $ so that if there is a solution to the original problem, it becomes two in the new one. In this formulation, it looks to me like there is the same number of solutions and you have to pick $ 2 $ every time.  
> **username_0**: Sorry, I meant $ K' = 8 * K + 1 $.  
> **username_1**: @username_0 in your version there is no distinction between the two $1$s so the solution counts as one. And also in my answer an original solution $Y$ becomes two: $Y \cup \{1,1\}$ and $Y \cup \{2\}$  

---

### Answer by username_0 on 2021-01-08. Score: 1

Yes, this appears to be true in the case that the integers are all positive. We simply take a Subset Sum instance defined by the set $ X = \{ x\_{1}, \ldots, x\_{n} \} $ and the target value $ K $ and create the set $ X' = X + \{ K \} $. Then there are at least two solutions to this problem if there is at least one to the original. Likewise, if there are two solutions given to this At Least Two Subset Sum problem; we simply pick either of them unless one of them is $ \{ K \} $, in which case we simply pick the other solution. Any solution to the At Least Two Subset Sum problem besides $ \{ K \} $ cannot have $ \{ K \} $ as a subset since $ K + \sum\_{ s \in S } s > K $ because all $ s $ are positive. So the other solution must solve the original problem.


---

