reducing subset-sum to partition

Question

Subset-sum: Given a list of numbers, find if a non-empty sublist has sum 0 (there's a variation where we want sum=k instead of 0, but 0 is easier for analysis)

Partition: Given a list, can it be partitioned into two non-empty sublists with equal sum?

I want to reduce subset-sum to partition. The reductions I found so far are same as this one but it has following faults :

1. For $B=0$, you can always partition $L'$ into $\{2S-0\}$, $\{S+0\} U L$.
2. It supposes $2S-B$ and $S+B$ have to go to different partitions! You could have both of them in same partition along with elements that sum to $-S$, hence total sum $= 2S$ as needed.

Answer 1

1. You're absolutely right that this partition always occurs. If you consider what this means in terms of the corresponding subset, you'll find that this indicates that the empty set (which is always a subset) has sum 0. In fact, this indicates the there is always a solution to subset sum when the target is 0, which is exactly as expected. It turns out fixing the target sum to 0 does not just make the problem easier to discuss, it makes it easier in a complexity sense ($O(1)$ by outputting YES immediately).

2. You're right here too. There is a formulation of subset sum where the input is a list of positive integers, and I think the reduction you are reading was from that language. The goal was to have our added elements be large enough that they cannot both go in the same part. To patch that up, we can use the sum of the absolute values. This actually shows some of the structure of the proof better, because $2S$ was actually $S +$ some-large-enough-number-for-which-$S$-will-suffice-but-so-do-larger-numbers.

At this point I'm copy-pasting from the linked post and just editing to handle negatives:

Let $(L,B)$ be an instance of subset sum, where $L$ is a list (multiset) of numbers, and $B$ is the target sum. Let $S = \sum L$ and choose $S' > \sum_{l \in L} |l|$. Let $L'$ be the list formed by adding $S'+B,S'+S-B$ to $L$.

(1) If there is a sublist $M \subseteq L$ summing to $B$, then $L'$ can be partitioned into two equal parts: $M \cup \{ S' + S-B \}$ and $L\setminus M \cup \{ S'+B \}$. Indeed, the first part sums to $B+(S'+S-B) = S'+S$, and the second to $(S-B)+(S'+B) = S'+S$.

(2) If $L'$ can be partitioned into two equal parts $P_1,P_2$, then there is a sublist of $L$ summing to $B$. The sum of the two new elements is $(S'+B)+(S'+S-B) = 2S'+S$. All subsets $A \subset L$ have $\left|\sum A\right| < S'$, so it is not possible that $\{S'+S-B\} \cup \{ S'+B \} \cup A$ has sum $S' + S$ (it is always greater). So the two new elements belong to different parts. Without loss of generality, $S'+S-B \in P_1$. The rest of the elements in $P_1$ belong to $L$ and sum to $B$; they do not include a new element, so they are a solution to subset sum.