# 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. – Acccumulation Jun 15 '18 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 '18 at 19:08
• What's the context where you encountered this problem? Can you credit the original source? – D.W. Jun 15 '18 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 '18 at 19:17

## 3 Answers

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.

• The question says they're all positive integers, but it's not clear that we can treat $S$ as a constant. – David Richerby Jun 15 '18 at 17:59
• S doesn't have to be constant, it's still O (nS). – gnasher729 Jun 15 '18 at 22:24
• 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. – David Richerby Jun 15 '18 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).