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