# How to reduce SUBSET-SUM with integers to SUBSET-SUM with non-negative integers?

The subset sum problem is as follows:

Given a sequence of integers $$\mathcal S=(a_1, ..., a_n)$$ with cardinality $$n$$ and an integer $$T$$, determine whether there is a subsequence of $$\mathcal S$$ whose sum equals $$T$$. Denote this problem $$SSP$$.

I was given a variant of the subset sum problem:

Given a sequence of $$\color{blue}{\mbox{non-negative}}$$ integers $$\mathcal S=(a_1, ..., a_n)$$ with cardinality $$n$$ and an integer $$T$$, determine whether there is a subsequence of $$\mathcal S$$ whose sum equals $$T$$. Denote this problem $$SSP_+$$.

My task is to prove that $$SSP\leq_p SSP_+$$ Therefore, I have to come up with a polynomial-time transformation $$f$$ between problem instances of $$SSP$$ and those of $$SSP_+$$, and prove the correctness of my reduction. This is where I encounter difficulties. I was given a hint:

Let $$L=(a_1,\cdots,a_n;T)$$ be a problem instance of $$SSP$$, then consider a transformation $$f$$ in the sense that $$f(a_1,\cdots,a_n;T)=(a_1+K,\cdots,a_n+K, \underbrace{K, \cdots,K}_{n\,K's};T+nK)$$ How do you choose $$K$$? And, when do you need to do the transformation? Don’t forget to justify that the answer to the problem instance $$L$$ is “yes” iff the answer to $$f(L)$$ is “yes”.

My Thoughts

I was thinking about assigning $$K$$ the value $$K=\sum_{i=1}^n|a_i|$$ so that there is no subsequence of $$\mathcal S$$ whose sum exceeds $$K$$. This $$K$$ ensures that $$a_i+K\geq 0$$ for $$1\leq i\leq n$$.

To me it's rather straightforward to show that $$\mbox{answer to }L\mbox{ is "yes"}\implies \mbox{answer to }f(L)\mbox{ is "yes"}$$ but I encounter serious difficulties proving the other direction. That's why I come here to seek help.

My Questions

Is my choice of $$K$$ correct? If so, how do I prove the other direction?

To prove the reverse direction you need to show that if there exist a subsequence $$S_1$$ in $$(a_1+K,a_2+K,\dotsc,a_n+K,K,\dotsc,K)$$ that sums to $$T+nK$$, then there is a subsequence $$S_2$$ in $$(a_1,\dotsc,a_n)$$ that sums to $$T$$.
The proof would become easy if we assume that $$S_1$$ only contains $$n$$ elements. If that happens, then the above statement holds. (hope you can prove this on your own).
Now, we need to make sure that $$S_1$$ contains exactly $$n$$ elements for its sum to be $$T+nK$$. Note that it is possible when $$K$$ is super large. If $$K$$ is super large and $$S_1$$ contains more than $$n$$ elements, then sum of $$S_1$$ $$>$$ $$T+nK$$. Similarly, if $$K$$ is super large and $$S_1$$ contain less than $$n$$ elements, then sum of $$S_1$$ $$<$$ $$T+nK$$.
Therefore, better choose $$K$$ to be at least $$|T| + \sum_{i = 1}^n|a_i|$$.
Your choice of $$K$$ is problematic. For example, consider sequence $$(-1,-1)$$ and $$T=2$$ (which is a no instance). Here $$K = \sum_{i = 1}^n |a_i| = 2$$. This sequence reduces to sequence $$(1,1,2,2)$$ and $$T = 6$$, which is a yes instance.