I recently had a google phone screen where i was asked the following question.

Given an array of n integers ( -1e9 <= A[i] <= 1e9 ) return top k combination sum where k <= 1500, n <= 1e5

eg. if n = 4, array = [8, 4, 2], k = 3, the answer will be [14, 12, 10] corresponding to the combinations (8, 4, 2), (8, 4) and (8, 2).

I only know the backtracking solution. How to solve this efficiently?