Esiste un algoritmo $ O (n^2) $ o $ o (n^3) $ per verificare se un numero è una somma di $ k $ elementi di array ordinato?

Question

Lascia che $ A $ sia un array ordinato di numeri interi positivi $ n $ (ordinato in ordine non di riduzione, cioè ci possono essere uguali elementi consecutivi). Possiamo verificare se un numero intero positivo $ x $ è una somma di $ k $ elementi di $ a $ in $ o (n^2) $ o $ o (n^3) $ complessità tempo? Se sì quale sarebbe lo pseudocodice?

Questo sembra essere un problema dello zaino per me e secondo Wikipedia È un problema di completamento NP. Quindi, anche se l'array non fosse stato senza moto in primo luogo e volevamo risolverlo, ci vorrebbe $ O (n log n) $ tempo, il che non aiuta davvero se il problema è comunque completo. Eppure mi chiedo se potrebbe essere fatta un po 'di ottimizzazione per ottenere un tempo migliore.

Si prega di trattare $ x $ e $ k $ come costanti, per l'analisi del tempo di esecuzione.