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

Question

上次我发现了一个有趣的问题，然后就卡住了。

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

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

例如:
n = 4, k = 8
a = { 2, 7, 8, 15 }

1: { 2 }, 总和 = 2
2: { 7 }, 总和 = 7
3: { 8 }, 总和 = 8
4: { 2, 7 }, 总和 = 9
5: { 2, 8 }, 总和 = 10
6: { 7, 8 }, 总和 = 15
7: { 15 }, 总和 = 15
8: { 2, 15 }, 总和 = 17
...
k = 8，所以答案 = 17(子集 {2,15})。

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

Answer 1

(为简单起见，将假设非空子集。处理空子集是一两行。)

给定索引 S 的非空子集，将 S 的 children 定义为 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}

以相应数组元素的总和为键，这棵树是一个最小堆。如果您仔细计算 key (通过加减法而不是从头开始求和)并延迟执行最小堆删除，那么您会得到一个 O(k log k) 时间算法。