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\scriptsize{\mbox{'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?
Thanks for reading my post.
Your idea is correct and you are missing only a small step for the proof.
First of all, I would choose $$K = 1+\sum_{i=1}^n|a_i|$$ just to be safe. Note that by this choice, crucially, the sum $\tau$ of any subsequence of $\mathcal{S}$ is within $-K+1\leq\tau\leq K-1$.
I will only show the "$\Longleftarrow$" direction, since, as you mentioned, the other direction is immediate. For an easier notation, let's define $a_{n+1} = a_{n+2}=\dots=a_{2n}=0$. With this notation, the values of the sequence $f(\mathcal{S})$ are $(a_1+K,\dots,a_{2n}+K)$. Now, let $i_1,\dots,i_m \in \{1,2,\dots,2n\}$ be the indices of a length-$m$ subsequence of $f(\mathcal{S})$ that solves $f(L)$, i.e., $$ \sum_{r=1}^m (a_{i_r}+K) = T+nK. $$ and thus $$ \sum_{r=1}^m a_{i_r} + mK = T+nK. $$ Due to the above observation that the subset sum $\tau$ of any subsequence of $\mathcal{S}$ are within $-K+1\leq\tau\leq K-1$, it follows that only $m=n$ is possible, and thus $$ \sum_{r=1}^n a_{i_r} = T. $$ Removing all the values with $r>n$ from the subsequence (which are all $0$) gives then a solution to $L$.