Fancy, classic, STEP-BY-STEP Analysis strategy problem. Here is the approach:
1. Sort input arrays.. so sum[0] is a[0] * k, so we got a[0]
2. Then who is 2nd smallest? a[0] * (k-1) + a[1] - from a[0] to a[1], the strategy is pretty obvious now: we guess a[i] one by one
3. How do we guess a[i], when we have a[0]..a[i-1]? It will be the same problem after we remove all sums involving only a[0]..a[i-1]
4. Now the only problem is, how do we remove all sums involving a[0]..a[i-1]