Complexity of subset sum with multiple targets

Question

Is the following problem in NP-Complete or P?

Input: A set S of positive integers {a1, a2, ..., an) and a positive integer M
Question: Is there a subset S' of S such that all the elements in S' sum to either M-1, M or M+1.

My guess is that it is in NP-Complete and related to subset sum. However I'm having a hard time reducing Subset sum to this problem.

Answer 1

This is NP-complete. Given an instance of subset sum

Find a subset of {x1, ... xn} with sum X

Consider the following instance of your problem

Find a subset of {4 * x1, 4 * x2, ..., 4 * xn} with sum 4*X, 4*X-1 or 4*X + 1

By considering divisibility-by-4, it's clear that any subset which sums to 4*X, 4*X-1 or 4*X + 1 will actually have to sum to 4X. But that then trivially gives a solution to the original subset-sum problem, by dividing through by 4.