# Is there an $O(n^2)$ or $O(n^3)$ time algorithm to check if a number is a sum of $k$ elements of sorted array?

Let $A$ be a sorted array of $n$ positive integers (sorted in non-decreasing order, that is there can be equal consecutive elements). Can we check whether some positive integer $x$ is a sum of $k$ elements of $A$ in $O(n^2)$ or $O(n^3)$ time complexity? If yes what would be the pseudocode?

This seems to be a knapsack problem to me and according to Wikipedia it's an NP-complete problem. So even if the array was unsorted in the first place and we wanted to sort it it would take $O(n\log n)$ time which doesn't really help if the problem is NP-complete anyway. Yet I wonder if some optimization may be made to achieve better time.

Please treat $x$ and $k$ as constants, for running time analysis.

• All algorithms will clearly be constant-time, in terms of n. Jun 15, 2018 at 18:31
• What's $n$? Is $k$ to be treated as a constant? Is $x$ to be treated as a constant?
– D.W.
Jun 15, 2018 at 19:08
• What's the context where you encountered this problem? Can you credit the original source?
– D.W.
Jun 15, 2018 at 19:08
• @D.W. I edited the OP to add that $n$ is the length of the array. I did say in the OP that $x$ is a positive integer and also "$k$ elements of $A$" so yes they're constants. This is a personal question of mine so no source for it.
– Yos
Jun 15, 2018 at 19:17

• The question says they're all positive integers, but it's not clear that we can treat $S$ as a constant. Jun 15, 2018 at 17:59
• Sure but the question asks if it's possible in $O(n^2)$ or $O(n^3)$. If $S$ is part of the input, then $nS = O(n2^n)$ is about the best you can say (unless it's written in unary, in which case you get $O(n^2)$, as requested. Jun 15, 2018 at 22:42
If $x$ and $k$ are to be treated as constants, as you propose, then there is a solution with running time $O(n)$: use dynamic programming, and let $B[s,i,j]$ indicate whether there is a combination of $i$ elements from $A[1..j]$ that sums to $s$. The $B$ array can be filled in, in $O(nkx)=O(n)$ time, using dynamic programming.
In practice I'm skeptical that one can reasonably consider $x,k$ to be constants; unless $x,k$ are particularly small, calling this $O(n)$ running time might give a misleading impression about how fast it will be.
If you allow to use every number from the array only once then it is indeed a knapsack problem. If you can use every number multiple times then you consecutively generate sets of number which can be generated with sums of 1, 2, 3 ... k elements of the array. Every step is O(n*x). Overall complexity will be O(k*n*x).