问如果组的和至少为K，则从数组中选择元素的方法数

EN

对于这个问题，您可以使用类似于通常用于在时间O(N*2^(N/2))中解决子集和问题的“中间技巧”(meet in the中间技巧)(并且您将具有相同的复杂性)。

首先，计算第一个2^N/2元素的可能和，并存储它们。对最后一个N/2元素也做同样的操作。

现在，两种排序都是按递增顺序排列的。对n元素进行排序需要时间( O(n log n) )，因此这里需要O(N 2^(N/2))成本。让我们调用这两个排序集F和L (对于第一个和最后一个)。

然后，执行以下操作：

设res =0 对于I从0到2^(N/2)-1{ 在{0，..,2^(N/2)-1}中找到最小的..，2^，使Fi + Lj_i >= K(对此使用二次搜索) 如果存在这样的j_i，则将res增加(2^(N/2) - j_i) } 返回区域

这样做的想法是，对于第一个N/2元素的每个子集，您将看到有多少种方法可以选择最后一个N/2元素的子集，以使总和高于K。为此，您只需在最后一个元素子集的和中找到实现这一目标的最低值，然后您就知道，与值之和至少一样大的子集恰恰是与大于或等于K的初始子集组合在一起的子集，计算这些子集很容易，因为您对可能值的数组进行了排序。

P.S :边际优化是可能的，通过使用最小j_i序列，使F[i] + L[j_i] >= K是一个不增加的序列。