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?
Thanks for reading my post.