Find the kth minimum sum of all possible subsets

Question

Last time I found an interesting problem, and I got stuck on it.

For n numbers a [1], ..., a [n] in increasing order and the number k (1 <= n, k <= 10 ^ 5).

Let's say that we sort all possible subsets of a given sequence by sum. We must find the sum of the kth such subset.

For instance:
n = 4, k = 8
a = {2, 7, 8, 15}

1: {2}, sum = 2
2: {7}, sum = 7
3: {8}, sum = 8
4: {2, 7}, sum = 9
5: {2, 8}, sum = 10
6: {7, 8}, sum = 15
7: {15}, sum = 15
8: {2, 15}, sum = 17
...
k = 8, so the answer = 17 (a subset of {2,15}).

Of course, we can generate all possible subsets, and the whole solution works in O (2 ^ n * n), but I'm looking for something more intelligent - linear or at least O (nk).

Answer 1

(It is assumed that for simplicity, a non-empty subset is assumed. Processing an empty subset is a string or two.)

Given a nonempty subset of indices S , define the children of S as S \ {max(S)} U {max(S) + 1} and SU {max(S) + 1} . Starting from {1} , the child relation forms a tree containing all nonempty subsets of natural numbers.

 {1} | \ {2} {1,2}______ | \ \ \ {3} {2,3} {1,3} {1,2,3} 

Using the sum of the corresponding array elements, this tree is a mini-heap. If you carefully calculate the keys (adding and subtracting, rather than summing from scratch) and delete the min-heap lazily, then you get the O (k log k) algorithm.