找到每个可能子集的第k个最小和

Question

上次我发现有趣的问题,我被困在上面.

给定n个数a [1],...,a [n]按升序排列,数字k(1 <= n,k <= 10 ^ 5).

假设我们用sum对每个可能的给定序列子集进行排序.
我们必须找到第k个这样的子集的总和.

例如:
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,所以answer = 17(子集{2,15}).

当然,我们可以生成每个可能的子集,整个解决方案在O(2 ^ n*n)中运行,但我正在寻找更智能的东西 - 线性,或至少O(nk).

Answer 1

(为简单起见,假设非空子集.处理空子集是一行或两行.)

由于指数的非空子集S,定义了孩子们的S是S \ {max(S)} U {max(S) + 1}和S U {max(S) + 1}.从...开始{1},子关系形成一个树,其中包括每个非整数的正整数子集.

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

以相应数组元素的总和为关键点,该树是一个小堆.如果你仔细计算密钥(通过添加和减去而不是从头开始求和)并且懒惰地实现最小堆删除,那么你得到一个O(k log k)-time算法.