Combination Sum

Kombinacja jest w pełni opisana przez liczbę kopii każdego kandydata, których używa. Dla [6, 2, 3] i wartości docelowej 8 odpowiedź [2, 3, 3] oznacza jedną 2, dwie 3 i żadnej 6. Jednym ze sposobów znalezienia wszystkich odpowiedzi jest więc wypróbowanie każdej możliwej liczby kopii każdego kandydata i zachowanie tych wyborów, których suma jest dokładnie równa target. Kandydat c może wystąpić najwyżej target / c razy, więc jego liczba kopii mieści się w zakresie od 0 do tej granicy.

Wyobraź sobie drzewo decyzyjne z jednym poziomem na kandydata, po ich posortowaniu. Na poziomie i decydujesz, ile kopii i-tej wartości wziąć, a każdy liść na dole odpowiada jednemu pełnemu zestawowi wybranych liczb kopii. Każdy multizbiór ma dokładnie jedną listę liczb kopii, więc żadna kombinacja nie zostanie znaleziona dwa razy. Próbowanie największej liczby kopii w pierwszej kolejności zapewnia też wymaganą kolejność: gdy dwie odpowiedzi po raz pierwszy różnią się liczbą kopii jakiejś wartości, ta, która ma ich więcej, nadal zawiera tę małą wartość, podczas gdy druga ma już większą, więc pojawia się jako pierwsza.

Problemem jest rozmiar drzewa. Liczba liści to iloczyn target / c + 1 dla wszystkich kandydatów: dla posortowanej listy [2, 3, 6] i wartości docelowej 8 daje to 5 × 3 × 2 = 30 liści dla 3 odpowiedzi. Każdy kandydat większy niż target / 2 podwaja liczbę liści, mimo że może wystąpić najwyżej raz, więc już 40 takich kandydatów oznacza 2^40, czyli około 10^12 liści. Duże testy są skonstruowane właśnie w ten sposób i to podejście nie jest w stanie ich ukończyć.

Buduj każdą kombinację po jednej wartości, tak jakbyś ją zapisywał: w kolejności rosnącej. Indeks początkowy wymusza tę kolejność. Po dodaniu nums[i] kolejną wartością może być ponownie nums[i], ponieważ kandydat może się powtarzać, albo dowolna późniejsza wartość, ale nigdy wcześniejsza. Dlatego wywołanie, które dodało indeks i, wykonuje pętlę tylko od i wzwyż. Każda kombinacja ma dokładnie jedną kolejność rosnącą, więc odpowiada jej dokładnie jedna ścieżka w drzewie, a duplikat taki jak [3, 2, 3] nigdy nie powstaje.

Oto całe drzewo dla posortowanej tablicy [2, 3, 6] i celu 8. Korzeń ma 8 do wykorzystania i próbuje wartości 2, 3 oraz 6. Po wybraniu 2 zostaje 6. Po wybraniu 2, 2 zostają 4, a po 2, 2, 2 zostają 2; dodanie jeszcze jednej 2 daje odpowiedź [2, 2, 2, 2]. Po 2, 2, 3 zostaje 1 i ścieżka kończy się niepowodzeniem. Po 2, 3 zostają 3 i można spróbować tylko wartości 3 i 6; wartość 3 daje [2, 3, 3]. Po 2, 6 nic nie zostaje: [2, 6]. Po wybraniu 3 można spróbować tylko wartości 3 i 6, a po 3, 3 zostają 2, których nie da się uzupełnić. Po wybraniu 6 zostają 2 i można spróbować tylko 6. Łącznie dwanaście wywołań, w porównaniu z 30 liśćmi w pierwszym podejściu.

Sortowanie zmienia ślepą uliczkę we wczesne zakończenie. Gdy nums[i] jest większe niż pozostała wartość, każda późniejsza wartość również jest większa, więc kończysz pętlę za pomocą break, zamiast sprawdzać pozostałe wartości. W powyższym drzewie węzeł 2, 2, 3 z pozostałą wartością 1 sprawdza 3, widzi, że ta wartość się nie mieści, i nie sprawdza już 6. Wyszukiwanie odwiedza tylko te prefiksy, których suma nadal nie przekracza target; dlatego duże testy, które spowalniają pierwsze podejście, wymagają tutaj tylko kilku tysięcy wywołań.

Kolejność wyników wynika z tego samego przejścia. Na każdym poziomie pętla najpierw próbuje mniejsze wartości, a każda kombinacja jest zapisywana w kolejności rosnącej. Dwie odpowiedzi po raz pierwszy różnią się na poziomie, na którym rozdzielają się ich ścieżki; ścieżka z mniejszą wartością na tym poziomie jest przeszukiwana jako pierwsza, więc odpowiedzi pojawiają się w porządku leksykograficznym. Jedna kombinacja nigdy nie może być prefiksem innej, ponieważ wartości są dodatnie i obie kombinacje osiągają tę samą sumę.