Максимальное количество чисел из массива, сумма которых не превосходит K

Здравствуйте. Дан массив A из N натуральных чисел. Нужно найти размер подмассива A максимальной длины, сумма элементов которого не превосходит K
Пример:
A = [1, 4, 2, 3] K = 6
Ответ: 3 (подмассив [1, 2, 3])
Правильно ли я думаю, что если отсортировать массив, то ответом будет количество первых элементов массива, сумма которых не превосходит К? И есть ли способ получше?

Ответ

Если ваша интерпретация постановки задачи действительно верна, то предложенный вам алгоритм - верен. Однако можно предложить более эффективное решение.
Вы можете применить обыкновенный алгоритм quick sort с дополнительной модификацией.
Если после выполнения partitioning оказывается, что сумма элементов в левой (меньшей) части массива не меньше чем K, то правая часть массива вас больше не интересует и тратить время на дальнейшую сортировку правой части никакого смысла нет. В случае же, когда сумма элементов в левой (меньшей) части массива меньше чем K, вы сразу знаете, что все элементы левой части заведомо входят в искомый подмассив и тратить время на дальнейшую сортировку левой части никакого смысла нет.
Это та же самая стратегия, по которой работает классический алгоритм поиска "k наименьших элементов", с той только разницей, что вы ищете не k наименьших элементов, а неизвестное число наименьших элементов, чья сумма не превосходит K
Таким образом на каждом уровне рекурсивного подразбиения вам нужно выполнять рекурсивный вызов только для одной половины подразбиения, в то время как вторая половина либо полностью игнорируется, либо просто целиком отправляется на выход (и затем игнорируется). Такой алгоритм должен легко допускать истинно циклическую реализацию, без использования стека.