Znajdź k-tą minimalną sumę każdego możliwego podzbioru

Question

Ostatni raz znalazłem interesujący problem i utknąłem na nim.

Podane n liczby a [1], ..., a [n] w porządku rosnącym i liczbie k (1 < = n, k < = 10^5).

Powiedzmy, że sortujemy każdy możliwy podzbiór danej sekwencji według sumy.
Musimy znaleźć sumę k-tego takiego podzbioru.

Na przykład
n = 4, k = 8
A = {2, 7, 8, 15}

1: {2} suma = 2
2: { 7} suma = 7
3: {8} suma = 8
4: {2, 7}, suma = 9
5: {2, 8} suma = 10
6: {7 8}, suma = 15
7: {15}, sum = 15
8: {2, 15}, suma = 17
...
k = 8, więc odpowiedź = 17 (podzbiór {2,15}).

Oczywiście możemy wygenerować każdy możliwy podzbiór i całe rozwiązanie działa w O (2^n * n), ale szukam czegoś bardziej inteligentnego - liniowego, lub przynajmniej O (nk).

Answer 1

(zamiar założyć niepuste podzbiory dla prostoty. Obchodzenie pusty podzbiór jest linia lub dwa).

Biorąc to niepusty podzbiór indeksów S zdefiniować dzieciom z S być S \ {max(S)} U {max(S) + 1} i S U {max(S) + 1}. Począwszy od {1}, relacja potomna tworzy drzewo, które zawiera każdy niepustny podzbiór dodatnich liczb całkowitych.

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

Kliknięta sumą odpowiednich elementów tablicy, to drzewo jest stosem min. Jeśli ostrożnie obliczysz klucze (dodając i odejmując zamiast sumowania od zera) i zaimplementujesz leniwie kasowanie min-kupka, otrzymasz algorytm O (k log k) -time.