Map subset sum with negative numbers

Viewed 89

The subset sum problem is defined as following:

Given a set of positive integers s₁,...,sₙ, is there a subset A of {1,...,n} such that the sum over A gives the positive integer T?

I know that the problem can be solved recursively even with negative values for s₁,...,sₙ and T, but I need to show explicitly that there is a mapping between the "signed" subset sum and the original one. Formally I need the reduction

SIGNED SUBSET SUM ≤ SUBSET SUM.

Thank you for your time!

0 Answers
Related