2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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)$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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[0]=S[1]=S[2]=true$. In general, your algorithm will always output $true$ if $1$ is in the input, which doesn't really make sense in this context. $\endgroup$
    – nir shahar
    Sep 25 at 0:28
  • $\begingroup$ @nirshahar. Right! I fixed my answer. $\endgroup$
    – Steven
    Sep 25 at 9:45
  • $\begingroup$ Sounds correct now! :) $\endgroup$
    – nir shahar
    Sep 25 at 10:20

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.