# Complexity of a variant of Subset Sum problem

This is the variant of SSP: Given $$n$$ positive integer points $$a_1, \ldots, a_n$$ which are all at most $$n$$, does there exist a subset $$\{a_i\}_{i \in P}$$, such that its summation is exactly $$n+1$$?

My question is, for general $$n$$, is this problem NP-hard?

The problem is polynomial-time solvable using a reduction to 0-1 knapsack problem. Take a knapsack of size $$W = n+1$$. Take $$n$$ items of size $$a_i$$ and value $$a_i$$. The maximum value obtained is $$n+1$$ if and only if there exists a subset of items that sum to $$n+1$$.

The 0-1 knapsack problem can be solved in time $$O(n \cdot W)$$ using dynamic programming. Therefore, the running time of the algorithm here is $$O(n^2)$$.

No (unless $$\mathsf{P}=\mathsf{NP}$$), the problem is in $$\mathsf{P}$$. The following is polynomial-time dynamic programming algorithm.

For $$i=0,\dots,n$$ and $$j=0, \dots, n+1$$ let $$S[i,j]$$ be true iff there exists a subset of $$\{a_1, \dots, a_i\}$$ whose elements sum up to $$j$$. We trivially have that $$S[i,0]$$ is true for all $$i$$, while $$S[0,j]$$ if false for all $$j>0$$. Moreover, for $$i,j>0$$ we have: $$S[i,j]= \begin{cases} S[i-1,j] & \mbox{if } a_i > j \\ S[i-1,j] \vee S[i-1, j-a_i] & \mbox{otherwise} \end{cases}.$$

The instance admits a solution if and only if $$S[n, n+1]$$ is true.

• Wont this count a certain element more than once? For example, given the singe integer $1$, there is no way to get a subset of sum $n+1=2$, since the only two subsets have sum $1$ or $0$. Your algorithm, will give $S=S=S=true$. In general, your algorithm will always output $true$ if $1$ is in the input, which doesn't really make sense in this context. Sep 25 at 0:28
• @nirshahar. Right! I fixed my answer. Sep 25 at 9:45
• Sounds correct now! :) Sep 25 at 10:20