Subset sum problem, given that a valid subset exists

Question

I have a problem at work. I need to find a subset of a set of positive integers that sums to a certain value. I know there is a subset but I need to find it. Is this new problem the same as the subset sum problem?

Answer 1

This problem is as hard as the primary subset sum problem.

Suppose you have a polynomial time algorithm (say the time with input size $n$ is bounded by a polynomial $f(n)$) for this problem, then for any instance of size $n$ of the primary subset sum problem, you can run this algorithm directly with at most $f(n)$ time. If the instance indeed has a solution, this algorithm will return a valid solution. Otherwise, this algorithm will return nothing, a meaningless string, or a wrong solution, etc. Anyway, the algorithm returns a valid solution if and only if the instance has a valid solution, and you can check in polynomial time whether this algorithm returns a valid solution. This results in a polynomial time algorithm for the primary subset sum problem.