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?
voila, S is your ans
Thanks dGreen. This is so elegant.
I'm not sure if it is the correct soln
Maybe a case where adding ith element again will be better. Like if top two maximum num are 20, 19 and A[i] = -2, A[i+1] = -10 then it makes sense to add -2 to 20 as well as 19. Our current soln will add -2 to 20 and -10 to 19.
Edited, This one should be correct
I think this can be solved using Fracturing Search. To handle the different sizes of each possible subset, we can insert $$$n$$$ $$$0$$$'s into the array. Thus, on your example, $$$(8, 4, 2), (8, 4), (8, 2)$$$ can be seen as $$$(8, 4, 2), (8, 4, 0), (8, 2, 0)$$$. CMIIW.
can you elaborate a bit more
Consider the simpler version of the problem:
Given an array $$$A$$$ of $$$N$$$ integers, you need to find $$$K$$$-th maximum sum subsequence of fixed size $$$L \leq N$$$.
For example, if $$$A = [9, 6, 4, 2, -1, -3]$$$, these are the subsequences of size $$$L = 3$$$ sorted by their sum:
Among all $$$\binom{N}{L}$$$ subsequences, the $$$3$$$-rd subsequence is $$$[9, 4, 2]$$$. This simpler version of the problem can be solved using Fracturing Search.
By inserting $$$N$$$ $$$0$$$'s into $$$A$$$, I was trying to reduce the original problem into the simpler version. Now, we are trying to find the $$$K$$$-th maximum sum subsequence of fixed size $$$N$$$ from the new array $$$A$$$ (new length is $$$2N$$$).
Using the previous example, $$$A$$$ would now become $$$[9, 6, 4, 2, \underbrace{0, 0, 0, 0, 0, 0}_{N}, -1, -3]$$$ and these would be its length $$$N$$$ subsequences:
However, this approach is apparently wrong because we would end up with a total of $$$\binom{2N}{N}$$$ subsequences instead of $$$2^N$$$ subsequences.
If we insist on solving the original problem using Fracturing Search, we would have to run $$$N$$$ separate fracturing searches simultaneously for each $$$1 \leq L \leq N$$$ and maintain it using something like Segment Tree.
Divide the array into two sets let call them A and B, where all the positive elements will be in A, and negative in B, find the top K sum in both the set individually, and then use a priority queue to find the top K from both A and B.
Top K for each set can be found by sorting and some observations.
Very interesting problem thought.
Let's make simpler the problem
How would why handle this case — -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -4 and k = 1000
I am not sure that taking only 11 elements would work.
Agree, needs to be considered all as well for negative