1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, now I can stop thinking about this. The input size will not exceed 20, so I will just generate the powerset and try each. But at least I can stop looking for a clever solution. $\endgroup$ – JRG Nov 23 '18 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.