Combination Sum

Q: Jaka jest złożoność czasowa problemu Combination Sum?

Wyszukiwanie z nawrotami ma złożoność wykładniczą. Przy n kandydatach, wartości docelowej t i najmniejszym kandydacie m kombinacja zawiera najwyżej t/m wartości, przy najwyżej n możliwościach wyboru każdej z nich: O(n^(t/m)) . Dodatkowa pamięć to O(t/m) na ścieżkę i stos wywołań, nie licząc wyniku.

Q: Dlaczego w Combination Sum wywołujesz rekurencję z i, a nie z i + 1?

Rekurencja z i pozwala, aby następną wartością ponownie był ten sam kandydat, dzięki czemu wartość może zostać użyta więcej niż raz. Rekurencja z i + 1 przesuwa się dalej, więc każdy kandydat może zostać użyty najwyżej raz.

Q: Czy problem Combination Sum można rozwiązać za pomocą programowania dynamicznego?

Tak. Dla każdej sumy od 0 do target przechowuj kombinacje, które ją osiągają, dodając po jednym kandydacie naraz, tak aby każda lista pozostawała uporządkowana rosnąco. Algorytm nigdy nie eksploruje dwa razy ślepej uliczki, ale przechowuje każdą częściową kombinację dla każdej sumy, co wymaga znacznie więcej pamięci. Ponieważ sam wynik może mieć rozmiar wykładniczy, zwykle stosuje się rekurencyjne przeszukiwanie z nawrotami.

ŚrednieNawroty

+10

Otrzymujesz listę candidates zawierającą różne dodatnie liczby całkowite oraz dodatnią liczbę całkowitą target. Znajdź wszystkie kombinacje liczb z listy, których suma wynosi dokładnie target. Każdej liczby możesz użyć dowolną liczbę razy. [2, 3, 3] i [3, 2, 3] to ta sama kombinacja.

Zwróć każdą kombinację w kolejności rosnącej, a kombinacje w porządku leksykograficznym: w pierwszej pozycji, na której dwie kombinacje się różnią, najpierw umieść tę z mniejszą wartością.

Funkcja

combinationSum(candidates: integer-array, target: integer) → integer-2d-array

candidatesinteger-array: różne wartości, których możesz używać, w dowolnej kolejności i dowolną liczbę razy
targetinteger: każda suma kombinacji musi wynosić dokładnie
Zwracainteger-2d-array: każda kombinacja, której suma jest równa wartości docelowej, każda w kolejności rosnącej, uporządkowane leksykograficznie

Ograniczenia

1 ≤ candidates.length ≤ 50
2 ≤ candidates[i] ≤ 500
2 ≤ target ≤ 500
Wszystkie wartości w candidates są różne i nie są uporządkowane w żaden szczególny sposób.
Co najmniej jedna kombinacja osiąga target, a najwyżej 150 kombinacji.

Przykłady

Wejście: candidates = [6, 2, 3]target = 8
Wyjście: [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
Wyjaśnienie: Cztery 2, 2 + 3 + 3 i 2 + 6 dają 8, uporządkowane według drugiej wartości. Bez 2 pozostają tylko 3 i 6, a ich sumy są wielokrotnościami 3, czym 8 nie jest.

Wejście: candidates = [5, 3, 4]target = 11
Wyjście: [[3, 3, 5], [3, 4, 4]]
Wyjaśnienie: 3 + 3 + 5 i 3 + 4 + 4 dają 11, a [3, 3, 5] występuje jako pierwsza, ponieważ jej druga wartość, 3, jest mniejsza niż 4. Żadne połączenie samych 4 i 5 nie daje 11.

Pytanie dodatkowe

Każdy kandydat może być teraz użyty najwyżej raz, a candidates może zawierać powtarzające się wartości. Jak zmienić wyszukiwanie, aby żadna kombinacja nie pojawiała się dwa razy?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Pułapka polega na zbudowaniu tej samej kombinacji dwa razy: 2, 3, 3 i 3, 2, 3 to ta sama odpowiedź. Buduj każdą kombinację w kolejności rosnącej, aby miała dokładnie jedną ścieżkę, i sortuj kandydatów, żeby gałąź kończyła się, gdy tylko następna wartość jest większa od tego, co pozostało.

Wypróbuj każdą liczbę dla każdego kandydata

Poprawne, ale nie kończy się na największych testach

Intuicja

Kombinacja jest w pełni opisana przez liczbę kopii każdego kandydata, które wykorzystuje: [2, 3, 3] to jedna 2, dwie 3 i żadnej 6. Wypróbuj każdą liczbę dla każdego posortowanego kandydata, od target / c do 0, zachowując te wybory, których suma wynosi dokładnie target. Każda kombinacja ma jedną listę liczebności, więc żadna nie zostanie znaleziona dwukrotnie. Najpierw większe liczebności dają porządek leksykograficzny: gdy dwie odpowiedzi różnią się po raz pierwszy, ta z większą liczbą kopii danej wartości nadal zawiera tę wartość, podczas gdy druga zawiera większą.

Dla [2, 3, 6] i wartości docelowej 8 istnieje 5 × 3 × 2 = 30 liści dla 3 odpowiedzi. Każdy kandydat większy niż target / 2 podwaja liczbę liści, więc 40 takich kandydatów oznacza 2^40, czyli około 10^12.

Algorytm

Posortuj kandydatów i zachowaj po jednym liczniku dla każdej wartości.
W choose(i, total) wypróbuj każdą liczbę k od target / nums[i] do 0 i wywołaj choose(i + 1, total + k × nums[i]).
Gdy każda wartość ma już przypisaną liczbę, zachowaj kombinację, jeśli total jest równe target, i zapisz ją na podstawie liczników.
Wywołaj choose(0, 0).

def combinationSum(candidates, target):
    nums = sorted(candidates)
    counts = [0] * len(nums)
    result = []

    def choose(i, total):
        if i == len(nums):
            if total == target:
                combo = []
                for value, k in zip(nums, counts):
                    combo.extend([value] * k)
                result.append(combo)
            return
        # Most copies first, so the combinations come out in lexicographic order.
        for k in range(target // nums[i], -1, -1):
            counts[i] = k
            choose(i + 1, total + k * nums[i])
        counts[i] = 0

    choose(0, 0)
    return result

Cofaj się w kolejności rosnącej i przycinaj

Intuicja

Po umieszczeniu nums[i] następna wartość może być ponownie nums[i] lub dowolną późniejszą wartością, nigdy wcześniejszą. Kombinacja ma dokładnie jeden porządek rosnący, więc ma dokładnie jedną ścieżkę, a [3, 2, 3] nigdy nie zostaje utworzona.

Dla posortowanej tablicy [2, 3, 6] i celu 8 ścieżki 2, 2, 2, 2 oraz 2, 3, 3 i 2, 6 dają 8. Ścieżka 2, 2, 3 pozostawia 1 i zatrzymuje się bez sprawdzania 6, a 3, 3 pozostawia 2, do którego nie pasuje żadna wartość. To 12 wywołań zamiast 30 liści w przypadku zliczania.

Na każdym poziomie pętla najpierw próbuje mniejszych wartości, więc odpowiedzi pojawiają się w kolejności leksykograficznej. Żadna odpowiedź nie jest prefiksem innej, ponieważ wartości są dodatnie i obie dają tę samą sumę.

Algorytm

Posortuj kandydatów.
W backtrack(start, remaining) zapisz kopię współdzielonej path, gdy remaining wynosi 0.
W przeciwnym razie przechodź pętlą przez i od start. Jeśli nums[i] > remaining, przerwij: każda kolejna wartość jest większa.
Dodaj nums[i], wywołaj backtrack(i, remaining - nums[i]), a następnie usuń ten element.
Wywołaj backtrack(0, target) i zwróć zapisane kombinacje.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break  # sorted, so every later value is too big as well
            path.append(nums[i])
            backtrack(i, remaining - nums[i])  # i, not i + 1: nums[i] may repeat
            path.pop()

    backtrack(0, target)
    return result

Pułapki i przypadki brzegowe

Przechodzenie przez wszystkich kandydatów na każdym poziomie zamiast zaczynać od bieżącego indeksu. [2, 3, 3], [3, 2, 3] i [3, 3, 2] są wtedy traktowane jako trzy różne odpowiedzi.
Rekurencyjne wywoływanie funkcji z i + 1 zamiast z i. Każda wartość może wtedy pojawić się tylko raz, więc [2, 2, 2, 2] zostaje pominięte.
Zapisywanie samej zmiennej path zamiast jej kopii. Każda zapisana odpowiedź jest wtedy tą samą listą, którą mechanizm cofania zmian opróżnił do końca.
Używanie break dla kandydatów, których nie posortowano. Przy [6, 2, 3] i pozostałej wartości 2 pętla zatrzymuje się na 6 i nigdy nie sprawdza 2.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu Combination Sum?

Wyszukiwanie z nawrotami ma złożoność wykładniczą. Przy n kandydatach, wartości docelowej t i najmniejszym kandydacie m kombinacja zawiera najwyżej t/m wartości, przy najwyżej n możliwościach wyboru każdej z nich: O(n^(t/m)). Dodatkowa pamięć to O(t/m) na ścieżkę i stos wywołań, nie licząc wyniku.

Dlaczego w Combination Sum wywołujesz rekurencję z i, a nie z i + 1?

Rekurencja z i pozwala, aby następną wartością ponownie był ten sam kandydat, dzięki czemu wartość może zostać użyta więcej niż raz. Rekurencja z i + 1 przesuwa się dalej, więc każdy kandydat może zostać użyty najwyżej raz.

Czy problem Combination Sum można rozwiązać za pomocą programowania dynamicznego?

Tak. Dla każdej sumy od 0 do target przechowuj kombinacje, które ją osiągają, dodając po jednym kandydacie naraz, tak aby każda lista pozostawała uporządkowana rosnąco. Algorytm nigdy nie eksploruje dwa razy ślepej uliczki, ale przechowuje każdą częściową kombinację dla każdej sumy, co wymaga znacznie więcej pamięci. Ponieważ sam wynik może mieć rozmiar wykładniczy, zwykle stosuje się rekurencyjne przeszukiwanie z nawrotami.

def combinationSum(candidates, target):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

candidates = [6, 2, 3]
target = 8

Oczekiwany wynik

[[2, 2, 2, 2], [2, 3, 3], [2, 6]]