# Subset Sum With Interval Integer Target

Define the subset sum with interval integer target problem (SSIITP) as follows:

SSIITP Input:

• A multiset $$S = \{a_1, …, a_p\}$$ of positive integers $$a_i$$.
• An integer $$T$$.

SSIITP Output:

• True, if there is a subset $$S’ \subseteq S$$ such that $$\sum_{x \in S'} x \in T .. 2T$$.
• False, otherwise.

Where $$a .. b$$, for two integers $$a$$ and $$b$$, is an integer interval including every integer between $$a$$ and $$b$$: $$a, a+1, a+2, \dots, b-2, b-1, b$$.

Is SSIITP NP-hard?

The problem is solvable in polynomial time and hence it is not $$\mathsf{NP}$$-hard (unless $$\mathsf{P}=\mathsf{NP}$$).

Here is a polynomial-time algorithm: assume without loss of generality that $$T \ge 1$$, that $$a_n > 2T$$, and that, for $$i=1,\dots,n-1$$, $$a_i \le a_{i+1}$$. Moreover, we can also assume that there is no $$a_j$$ that satisfies $$T \le a_j \le 2T$$ (since otherwise the answer is trivially "true").

Define $$\sigma(j) = \sum_{i=1}^j a_i$$. If there is any $$j \in \{1,\dots, n\}$$ that satisfies $$T \le \sigma(j) \le 2T$$ then $$\{a_1, \dots, a_j\}$$ is a feasible solution and the answer is "true".

On the contrary, if for every $$j$$ you have $$\sigma(j) < T$$ or $$\sigma(j)>2T$$, then you can immediately answer "false".

To see that this is indeed the case, define $$j^* \ge 1$$ as the smallest value of $$j$$ that satisfies $$\sigma(j)>2T$$ (notice that $$j^*$$ always exists since $$\sigma(n) \ge a_n > 2T$$). We must simultaneously have $$\sigma(j^*-1) < T$$ and $$\sigma(j^*) > 2T$$, hence $$a_{j^*} = \sigma(j^*) - \sigma(j^*-1) > T$$, which implies $$a_{j^*} > 2T$$.

Clearly, for all $$j \ge j^*$$ we have $$a_j \ge a_{j^*} > 2T$$ and hence no solution can possibly contain $$a_j$$. However, the sum of the elements in any subset of $$S \setminus \{a_{j^*}, \dots, a_n\} = \{a_1, \dots, a_{j^*-1}\}$$ can be at most $$\sigma(j^*-1). This shows that there is no feasible solution.

• In English: If there's a term whose value is between T and 2T, then it trivially satisfies the criteria; We can ignore any term whose value is >2T. It can't be part of a solution; If the remaining terms sum to <T there's no solution; Otherwise, we can start with the empty set and arbitrarily add terms to it until arriving at something which is >=T. Since no one term is >=T, it's not possible, by adding a single term, to have the sum jump from <T to >2T (since the new sum is just the old sum plus the new term) Nov 3, 2021 at 17:34
• @dspyz. Great explanation! A straightforward implementation of the algorithm in my answer requires time $\Theta(n \log n)$, while an implementation of the steps in your comment only requires linear time. (Perhaps the comment can be turned into an answer?) Nov 3, 2021 at 18:16