Для данного массива (предположим, что неотрицательные целые числа) мы должны найти подмножество наименьшей длины, чтобы сумма элементов была не меньше, чем K. K - другое целое число, представленное в качестве входных данных.

Возможно ли иметь решение с временной сложностью O (n) [большой ой из n]?

мое текущее мышление состоит в следующем: мы могли бы отсортировать массив в O (n * log n), а затем выполнить итерацию по отсортированному массиву, начиная с наибольшего числа и поддерживая текущую сумму, пока текущая сумма не станет> = K.

Однако это будет иметь худшее время выполнения O (n * (log n + 1)).

Поэтому, если бы кто-нибудь мог поделиться идеями сделать это в O (n) время, я был бы очень признателен ..

Примечание: элементы subarray не должны быть последовательной последовательностью исходного массива в этом контексте