Generowanie wszystkich podzbiorów
Wybieranie każdego elementu lub pomijanie go
Generowanie wszystkich podzbiorów to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Po co generować podzbiory
W wielu zadaniach konkursowych trzeba sprawdzić każdy podzbiór małego zbioru. Rekurencja pozwala przejrzyście i niezawodnie wypisać je wszystkie. 🧩
Wybór lub pominięcie każdego elementu
Najważniejsza idea jest prosta: dla każdego elementu podejmują Państwo jeden binarny wybór — dołączyć go albo pominąć. Każdy pełny zestaw wyborów tworzy jeden podzbiór.
Ile istnieje podzbiorów
Zbiór złożony z n elementów ma dokładnie 2 do potęgi n podzbiorów, ponieważ każdy element podwaja ich liczbę. Dlatego n powinno być małe, najlepiej nie większe niż około 20.
Plan rekurencyjny
Przesuwają Państwo indeks po tablicy. Na każdym indeksie rozgałęziają Państwo wykonanie na dwie ścieżki: jedną, która wybiera element, i drugą, która go pomija.
Przypadek bazowy
Gdy indeks wyjdzie poza ostatni element, bieżąca ścieżka jest jednym kompletnym podzbiorem. To jest Państwa przypadek bazowy, w którym należy go zapisać.
Rekurencja podzbiorów w kodzie
To rekurencyjne przejście zapisuje podzbiór na końcu, a następnie dla każdego indeksu sprawdza zarówno pominięcie, jak i wybranie elementu.
def gen(i, cur):
if i == len(a):
out.append(cur[:])
return
gen(i + 1, cur)
gen(i + 1, cur + [a[i]])Cofanie przez odwrócenie wyboru
Po dodaniu elementu należy usunąć go po zakończeniu rekurencji, aby następna gałąź zaczynała się od czystego stanu. To cofnięcie jest istotą przeszukiwania z nawrotami.
cur.append(a[i])
gen(i + 1, cur)
cur.pop()Alternatywa w postaci maski bitowej
Można również przypisać każdą liczbę całkowitą od 0 do 2 do potęgi n minus 1 do jednego podzbioru, przy czym każdy bit oznacza, czy dany element został dołączony.
for mask in range(1 << n):
sub = [a[i] for i in range(n) if mask >> i & 1]Przed zapisaniem utwórz kopię
Zawsze należy zapisywać kopię bieżącej listy, a nie samą listę. W przeciwnym razie późniejsze zmiany nadpiszą każdy zapisany podzbiór. ⚠️
Generowanie kombinacji
Aby uzyskać podzbiory o ustalonym rozmiarze k, należy zakończyć gałąź, gdy liczba wybranych elementów osiągnie k. W ten sposób podzbiory stają się kombinacjami.
Zastosowania podzbiorów
Generowanie podzbiorów rozwiązuje małe problemy plecakowe, zadania polegające na dobieraniu zespołów oraz sprawdzanie wykonalności, gdy trzeba przetestować każdy możliwy wybór.
Szybkie sprawdzenie
Ile podzbiorów ma zbiór złożony z n elementów?
Podsumowanie: rozgałęziaj się dla każdego elementu
Dowiedzieli się Państwo, jak wypisać wszystkie podzbiory, wybierając albo pomijając każdy element i cofając wybór po każdej gałęzi. Należy utrzymywać małe n, ponieważ liczba podzbiorów wynosi 2 do potęgi n. 🎯
Często zadawane pytania
Czy lekcja „Generowanie wszystkich podzbiorów” jest bezpłatna?
Tak — pełny tekst „Generowanie wszystkich podzbiorów” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Generowanie wszystkich podzbiorów”?
Wybieranie każdego elementu lub pomijanie go Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Generowanie wszystkich podzbiorów”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Myślenie rekurencyjne: baza i rekurencja
- Generowanie wszystkich podzbiorów
- Permutacje i idea N hetmanów
- Przycinanie, aby zmieścić się w limicie czasu