Dada una matriz (supongamos que no hay enteros no negativos) debemos encontrar el subconjunto de menor longitud, de modo que la suma de los elementos no sea menor que K. K es otro entero que se proporciona como entrada.

¿Es posible tener una solución con complejidad de tiempo O (n) [big oh of n]?

Mi idea actual se basa en las siguientes líneas: podríamos ordenar la matriz en O (n * log n) y luego iterar sobre la matriz ordenada a partir del número más grande y mantener la suma corriente hasta que la suma corriente se convierta en> = K.

Sin embargo, esto tendría el peor tiempo de ejecución de O (n * (registro n + 1)).

Entonces, si alguien pudiera compartir ideas de hacer esto en un momento O (n), realmente lo apreciaría ..

Nota: los elementos del subarray no tienen que ser una secuencia contigua de la matriz original en este contexto