Subsets

+10

Otrzymujesz listę nums zawierającą różne liczby całkowite. Zwróć każdy jej podzbiór, włącznie z pustym podzbiorem i całą listą, tak aby n wartości dawało 2^n podzbiorów. Zapisz wartości w każdym podzbiorze w kolejności rosnącej, a podzbiory wypisz w porządku leksykograficznym: porównuj podzbiory wartość po wartości — o kolejności decyduje pierwsza różnica, a podzbiór będący początkiem innego podzbioru występuje przed nim. Dla [1, 2] odpowiedzią jest [[], [1], [1, 2], [2]].

Funkcja

subsets(nums: integer-array) → integer-2d-array

numsinteger-array: wartości, wszystkie różne, w dowolnej kolejności
Zwracainteger-2d-array: każdy podzbiór, każdy posortowany rosnąco, wypisany w porządku leksykograficznym

Ograniczenia

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10
Wszystkie wartości w nums są różne.
nums mogą występować w dowolnej kolejności.

Przykłady

Wejście: nums = [3, 1, 2]
Wyjście: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Wyjaśnienie: Po posortowaniu wartości to 1, 2, 3, a trzy wartości dają 2^3 = 8 podzbiorów. [1, 2] występuje przed [1, 2, 3], ponieważ jest jego początkiem, a [1, 2, 3] występuje przed [1, 3], ponieważ 2 jest mniejsze od 3 na drugiej pozycji.

Wejście: nums = [0]
Wyjście: [[], [0]]
Wyjaśnienie: Jedna wartość ma dwa podzbiory: pomiń ją i otrzymaj [] albo wybierz ją i otrzymaj [0]. Pusty podzbiór zawsze jest pierwszy.

Wejście: nums = [5, -2]
Wyjście: [[], [-2], [-2, 5], [5]]
Wyjaśnienie: Wartości sortują się do -2 i 5, więc zapisujemy [-2, 5] w tej kolejności. Każdy podzbiór zawierający -2 znajduje się przed [5], ponieważ -2 jest mniejsze niż 5.

+13 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz utworzyć tę samą listę bez rekurencji, budując każdy podzbiór bezpośrednio na podstawie poprzedniego?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Istnieje 2^n podzbiorów, więc żadna metoda nie wykonuje mniej niż O(2^n) pracy. Pytanie brzmi, jak wygenerować każdy podzbiór dokładnie raz, w wymaganej kolejności, bez późniejszego sortowania 1024 list. Przeszukiwanie z nawrotami posortowanych wartości, z zapisywaniem każdego węzła drzewa decyzyjnego w chwili wejścia do niego, odwiedza podzbiory dokładnie w kolejności leksykograficznej.

Maski bitowe, a potem sortuj

Intuicja

Ułóż posortowane wartości na pozycjach od 0 do n-1. Podzbiór określa dla każdej pozycji, czy do niego należy, czy nie, i właśnie to robi n bitów liczby. Zatem liczby od 0 do 2^n-1 odpowiadają podzbiorom: dla [1, 2, 3] maska 5 ma postać binarną 101, ustawione są bity 0 i 2, a maska ta odpowiada [1, 3]. Maska 0 oznacza pusty podzbiór, a maska 7 — pełną listę.

Różne maski dają różne podzbiory, a każdy podzbiór ma swoją maskę, więc pętla generuje wszystkie 2^n podzbiorów dokładnie raz. Odczytywanie bitów od pozycji 0 wzwyż wśród posortowanych wartości powoduje, że każdy podzbiór jest zapisany w kolejności rosnącej.

Maski nie są generowane w kolejności wymaganej przez zadanie. Maska 1 to [1], maska 2 to [2], a maska 3 to [1, 2], więc [2] znalazłoby się przed [1, 2]. Rozwiążesz ten problem, sortując podzbiory za pomocą komparatora, który porównuje wartości po kolei i umieszcza prefiks przed dłuższym ciągiem. Sortowanie kosztuje więcej niż generowanie: dla 2^n podzbiorów potrzeba około n × 2^n porównań, a każde porównanie odczytuje do n wartości. Dla n = 10 to około 10^5 odczytów — nadal szybko, ale to praca, której następne podejście w ogóle nie wykonuje.

Algorytm

Posortuj nums, aby każdy podzbiór był uporządkowany rosnąco.
Dla każdej maski od 0 do 2^n-1 zbierz wartości z pozycji, których bity są ustawione.
Posortuj listę podzbiorów: na pierwszej pozycji, na której dwa podzbiory się różnią, wygrywa mniejsza wartość, a jeśli jeden kończy się wcześniej, umieść go jako pierwszy.
Zwróć posortowaną listę.

def subsets(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    for mask in range(1 << n):
        # Bit i of mask says whether values[i] is in this subset.
        result.append([values[i] for i in range(n) if (mask >> i) & 1])
    # Python compares lists position by position, and a prefix comes first.
    result.sort()
    return result

Cofanie się: wybierz, zbadaj, cofnij wybór

Intuicja

Wyobraź sobie podzbiory jako drzewo. Korzeniem jest zbiór pusty. Poniżej węzła możesz dodać dowolną wartość większą od ostatniej dodanej. Dla posortowanych wartości [1, 2, 3] korzeń ma dzieci [1], [2] i [3]; [1] ma dzieci [1, 2] i [1, 3]; [1, 2] ma dziecko [1, 2, 3]. Każdy podzbiór występuje w tym drzewie dokładnie raz, ponieważ można go zapisać rosnąco tylko na jeden sposób, a każdy węzeł jest odpowiedzią, nie tylko liście.

Algorytm nawrotów przechodzi po drzewie, używając jednej współdzielonej listy path. Aby przejść do dziecka, wybierasz: dodajesz wartość. Następnie eksplorujesz: wywołujesz rekurencję, a funkcja pomocnicza zapisuje kopię path w chwili, gdy do niej dociera. Potem cofasz wybór: usuwasz wartość, dzięki czemu path wraca do rodzica i można wypróbować następne rodzeństwo. Ponieważ każdy węzeł jest zapisywany przy wejściu do niego, rodzic zawsze jest zapisywany przed swoimi dziećmi.

Dlatego wynik jest uporządkowany leksykograficznie, bez sortowania. Dzieci węzła są sprawdzane od najmniejszej wartości wzwyż, a przejście kończy całą gałąź, zanim rozpocznie następną. Dla [1, 2, 3] zapisuje [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]: kolejność jak w słowniku, z prefiksem przed jego rozszerzeniami.

Drzewo ma 2^n węzłów, a kopiowanie ścieżki kosztuje do n, więc czas działania wynosi O(n × 2^n), czyli tyle, ile wynosi rozmiar samej odpowiedzi. Oprócz wyniku przechowujesz jedną ścieżkę i stos wywołań, oba o głębokości najwyżej n.

Algorytm

Posortuj wartości.
Napisz explore(start). Najpierw dodaje kopię path do wyniku.
Następnie dla każdego indeksu i od start do końca: dodaj values[i] do path (wybór), wywołaj explore(i+1) (eksploracja) i usuń ostatnią wartość (cofnięcie wyboru).
Wywołaj explore(0) z pustą ścieżką i zwróć wynik.

def subsets(nums):
    values = sorted(nums)
    result = []
    path = []

    def explore(start):
        # Every node of the decision tree is a subset: record it on the way in.
        result.append(path[:])
        for i in range(start, len(values)):
            path.append(values[i])  # choose
            explore(i + 1)          # explore: only larger values may follow
            path.pop()              # un-choose

    explore(0)
    return result

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi w tym zadaniu wynika z kolejności albo ze współdzielenia jednej listy.

Dodawanie samego path zamiast jego kopii. Każdy wpis wskazuje wtedy tę samą listę, która po zakończeniu przechodzenia jest pusta, więc zwracasz 2^n kopii [].
Zapomnienie o posortowaniu nums. Dla [3, 1, 2] drzewo tworzy [3, 1], co nie jest kolejnością rosnącą, a przechodzenie nie odbywa się już w kolejności leksykograficznej.
Zapisywanie wyników tylko w liściach, jak w przypadku permutacji. Każdy węzeł tego drzewa jest podzbiorem; zapisywanie tylko ścieżek, które docierają do końca, zwraca zbyt mało podzbiorów.
Rekurencja z start+1 zamiast i+1. Wartość może wtedy wystąpić po większej wartości, a nawet po sobie samej, przez co otrzymujesz listy takie jak [3, 2] i [3, 3], które nie są podzbiorami w kolejności rosnącej.
Używanie drzewa dołączania lub pomijania (decydujesz o wartości 0, potem o wartości 1 itd.) i zapisywanie wyników w liściach. Znajduje ono wszystkie 2^n podzbiorów, ale próba dołączania w pierwszej kolejności umieszcza pełną listę na początku, a próba pomijania w pierwszej kolejności umieszcza [3] przed [2]. Żadna z tych kolejności nie jest leksykograficzna.
Komparator, który najpierw sortuje według długości, daje [], [1], [2], [3], [1, 2], czyli inną kolejność.

Najczęstsze pytania4

Ile podzbiorów ma zbiór złożony z n elementów?

2^n. Każdy element albo należy do podzbioru, albo nie, niezależnie od pozostałych, więc liczba możliwości się mnoży: dwie dla pierwszego elementu, dwie dla drugiego i tak dalej. Trzy wartości dają 8 podzbiorów, a dziesięć — 1024, wliczając zbiór pusty i cały zbiór.

Jaka jest złożoność czasowa problemu podzbiorów?

O(n × 2^n). Istnieje 2^n podzbiorów, a zapisanie jednego z nich wymaga do n kroków, więc samo zwrócenie odpowiedzi kosztuje tyle samo. Algorytm nawrotów osiąga tę granicę i wykorzystuje tylko O(n) dodatkowej pamięci. Generowanie za pomocą masek bitowych jest równie szybkie, ale późniejsze sortowanie wyniku dodaje kolejny czynnik n.

Czy do podzbiorów używać nawrotów czy masek bitowych?

Maski bitowe są krótkie, nie wymagają rekurencji i sprawiają, że wybór „w zbiorze” lub „poza zbiorem” jest widoczny jako bity. Backtracking sam z siebie podaje podzbiory w porządku leksykograficznym i można go dostosować do popularnych wariantów: pomijania powtarzających się wartości, uwzględniania tylko podzbiorów o rozmiarze k lub tylko podzbiorów, których suma osiąga wartość docelową; w tym przypadku możesz wcześniej przerwać przeszukiwanie gałęzi.

Jak obsługiwać zduplikowane wartości w podzbiorach?

Posortuj wartości, a następnie w pętli funkcji pomocniczej do nawrotów pomijaj wartość, która jest równa poprzedniej na tym samym poziomie: i > start i values[i] == values[i-1]. Pierwsza kopia już sprawdza każdy podzbiór, który ją zawiera, więc gałąź równorzędna zaczynająca się od drugiej kopii odtworzyłaby jedynie te same podzbiory.

Python

def subsets(nums):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

nums = [3, 1, 2]

Oczekiwane

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]