Нахождение k элементов списка длины n, сумма которых меньше t за время O(nlogk)

Это из Programming Pearls ed. 2, столбец 2, задача 8:

Учитывая набор из n действительных чисел, действительное число t и целое число k, как быстро вы сможете определить, существует ли подмножество k-элементов множества, сумма которого не превышает t?

Одним из простых решений является сортировка и суммирование первых k элементов, что является нашей лучшей надеждой найти такую ​​сумму. Однако в разделе решений Бентли намекает на решение, требующее nlog(k) времени, хотя и не дает подсказок, как его найти. Я боролся с этим; одна мысль, которая у меня была, состояла в том, чтобы пройтись по списку и добавить все элементы меньше, чем t/k (за время O(n)); скажем, таких элементов m1 ‹ k, и их сумма равна s1 ‹ t. Затем нам нужно k - m1 элементов, поэтому мы можем снова просмотреть список за время O (n) в поисках всех элементов, меньших, чем (t - s1)/(k - m1). Снова добавьте, чтобы получить s2 и m2, затем снова, если m2 ‹ k, ищите все элементы меньше, чем (t - s2)/(k - m2). Так:

def kSubsetSumUnderT(inList, k, t):
    outList = []
    s = 0
    m = 0
    while len(outList) < k:
        toJoin = [i for i in inList where i < (t - s)/(k - m)]
        if len(toJoin):
            if len(toJoin) >= k - m:
                toJoin.sort()
                if(s + sum(toJoin[0:(k - m - 1)]) < t:
                    return True
                return False
            outList = outList + toJoin
            s += sum(toJoin)
            m += len(toJoin)
        else:
            return False

Моя интуиция подсказывает, что это может быть алгоритм O(nlog(k)) , но мне трудно доказать это самому себе. Мысли?