在一次采访中被问到这个问题，没有比生成所有可能的子集更好的答案了。示例：
a = [4,2,5,7] k = 8
output = 4
[2],[4,2],[2,5],[4,2,5]
面试官试图暗示对数组进行排序应该会有所帮助，但我仍然想不出比强力解决方案更好的方法。将感谢您的意见。
面试官暗示对数组进行排序会有所帮助，而且确实有所帮助。我会尽力解释的。
取您所述的数组和k值：
a = [4,2,5,7]
k = 8
对数组进行排序将产生：
a_sort = [2,4,5,7]
现在我们可以考虑以下程序：
集ii=0，jj=1
选择
a_sort[ii]作为子集的一部分2.1.如果是
2 * a_sort[ii] >= k，则完成。否则，子集[a_sort[ii]]保持条件并且是解的一部分。将
a_sort[ii+jj]添加到您的子集3.1.如果
a_sort[ii] + a_sort[ii+jj] < k，3.1.1.子集
[a_sort[ii], a_sort[ii+jj]]保持条件并且是解的一部分，以及由任何额外数量的元素a_sort[kk]组成的任何子集，其中ii< kk < ii+jj3.1.2.设置
jj += 1并返回步骤3。3.2.否则，
set ii += 1，jj = ii + 1，返回步骤2
根据您的输入，此过程应返回：
[[2], [2,4],[2,5],[2,4,5]]
# [2,7] results in 9 > 8 and therefore you move to [4]
# Note that for [4] subset you get 8 = 8 which is not smaller than 8, we are done
Explenation
- 如果[a_sort[ii]]的子集不包含
2 * a_sort[ii] < k，则向该子集添加额外的数字只会产生min(subset)+max(subset) > 2 * a_sort[ii] > k and therefore there will not be any additional subsets which hold the wanted condition. Moreover, by setting a subset of [a_sort[ii+1]] will results in2*a_sort[ii+1]>=2*a_sort[ii]>k`sinse a_sand被排序。因此，您将找不到任何其他子集 - 对于jj>ii，如果是
a_sort[ii] + a_sort[ii+jj] < k，那么您可以将来自a_sort的任何数量的if成员推送到子集中，只要索引kk将大于ii且低于ii+jj，因为a_sort是排序的，并且将这些成员添加到子集中不会改变min(subset)+max(subset)的值，而CCD_21将保持为a_sort[ii] + a_sort[ii+jj]，并且我们已经知道，由于k，该值较小
获取计数
如果你只是想得到可能的子集，这可以比生成子集本身更容易。
假设对于ii > jj，条件成立，即a_sort[ii] + a_sort[ii+jj] < k。如果CCD_ 26，则存在1个可能子集的加法。如果CCD_ 27，则存在CCD_。因此，总共有2**(jj-ii-1)个附加子集可用于添加到解决方案组(jj-ii-1个元素，每个元素独立存在或不存在(。这也适用于jj = ii + 1，因为在这种情况下2**(jj-ii-1) = 2**0 = 1
看看上面的例子：
- [2]加1个计数
- [2,4]加1个计数(
1 = 0 + 1( - [2,5]加2个计数(
2 = 0 + 2->2 **(2 - 0 - 1) = 2**1 = 2(
总共有4个
- 对数组进行排序
- 对于索引为
l的元素x，对数组进行二进制搜索，以获得数组中最大整数的索引，即< k-x。设索引为r - 对于
min(subset) = x所在的所有子集，我们可以拥有索引在(l,r]范围内的任何元素。具有min(subset) = x的子集的数目变为(r-l)元素的可能子集的总数，因此count=2^(r-l)(如果r<l，则为0(
(注意：在所有这些子集中，我们都在修复x。这就是为什么范围(l,r]不包括l的原因( - 您必须对数组进行迭代，对每个元素/索引使用上面的过程来获得子集的计数，其中我们的当前元素是最小的，并且子集满足给定的约束。如果找到一个具有
count=0的元素，请中断迭代
这应该适用于0(N*log(N))的复杂性，对于我的面试问题来说已经足够了。
对于给定的示例，排序数组=[2,4,5,7]。
2、l=0和r=2。计数=2^(2-0) = 4(包括[2],[4,2],[2,5],[4,2,5]
4、l=1和r=0。Count=0，然后我们中断迭代