Finden Sie k-th minimale Summe von jeder möglichen Untermenge

Question

Das letzte Mal fand ich interessante Problem, und ich steckte darauf fest.

Gegeben sind n Zahlen a [1], ..., a [n] in aufsteigender Reihenfolge und Zahl k (1 < = n, k < = 10^5).

Nehmen wir an, wir sortieren jede mögliche Teilmenge der gegebenen Sequenz nach der Summe.
Wir müssen die Summe der k-ten solchen Untermenge finden.

Zum Beispiel:
n = 4, k = 8
a = {2, 7, 8, 15}

1: {2}, SUM = 2
2: { 7}, sum = 7
3: {8}, sum = 8
4: {2, 7}, sum = 9
5: {2, 8}, sum = 10
6: {7, 8}, Summe = 15
7: {15}, Summe = 15
8: {2, 15}, Summe = 17
...
k = 8, also Antwort = 17 (Teilmenge {2,15}).

Natürlich können wir jede mögliche Teilmenge und ganze Lösung in O (2^n * n) generieren, aber ich suche nach etwas Intelligenterem - linear oder mindestens O (nk).

Answer 1

(nicht leere Teilmengen der Einfachheit halber annehmen, gehen. Die leere Teilmenge Handhabung ist eine Linie oder zwei.)

eine nicht leere Teilmenge von Indizes Bei S definieren die Kinder von SS \ {max(S)} U {max(S) + 1} und S U {max(S) + 1} zu sein. Beginnend mit {1} bildet die Kindbeziehung einen Baum, der jede nichtleere Untergruppe von positiven ganzen Zahlen enthält.

{1} 
| \ 
{2} {1,2}______ 
| \  \  \ 
{3} {2,3} {1,3} {1,2,3} 

Angepasst an die Summe der entsprechenden Array-Elemente ist dieser Baum ein Min-Heap. Wenn Sie die Schlüssel sorgfältig berechnen (durch Addieren und Subtrahieren statt durch Summieren) und die Min-Heap-Deletion langsam implementieren, erhalten Sie einen O (k log k) -Zeitalgorithmus.