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?

Question

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.

Answer 1

It depends on the numbers in the array. For example if all array elements are positive integers, and the requested sum is S, then O(nS) is easy.

Answer 2

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.

Answer 3

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