Podzbiory i zbiór potęgowy
Generować wszystkie podzbiory zbioru za pomocą przeszukiwania z nawrotami i masek bitowych, obsługując duplikaty przez sortowanie i pomijanie powtarzających się elementów
Podzbiory i zbiór potęgowy 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.
Podzbiory i zbiór potęgowy
Zbiór potęgowy zbioru S to zbiór wszystkich możliwych podzbiorów zbioru S, włącznie ze zbiorem pustym i samym zbiorem S. Zbiór zawierający n elementów ma dokładnie 2ⁿ podzbiorów. Dla [1, 2, 3] tych 8 podzbiorów to: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. Jest to fundamentalny problem kombinatoryczny, który pojawia się w pytaniach rekrutacyjnych dotyczących znajdowania wszystkich możliwych kombinacji, podziałów lub wyborów.
# A set of n elements → 2^n subsets
for n in range(5):
print(f'n={n}: {2**n} subsets')
# n=0: 1 (just the empty set)
# n=1: 2 ([], [x])
# n=2: 4 ([], [a], [b], [a,b])
# n=3: 8 (as enumerated above)
# n=4: 16Generowanie podzbiorów za pomocą backtrackingu
Należy użyć schematu wyboru–eksploracji–cofnięcia wyboru. Kluczowa decyzja projektowa polega na tym, aby podczas każdego wywołania rekurencyjnego natychmiast dodawać do wyników bieżącą częściową ścieżkę (zanim zostaną wybrane kolejne elementy). Dzięki temu każdy stan — pusty, częściowy i pełny — zostaje zapisany jako poprawny podzbiór. Indeks start należy przesuwać tak, aby rozpatrywać wyłącznie elementy znajdujące się na prawo od ostatnio wybranego elementu, co zapobiega duplikatom i zachowuje kolejność.
def subsets(nums):
result = []
def backtrack(start, path):
result.append(list(path)) # every state is a valid subset
for i in range(start, len(nums)):
path.append(nums[i]) # CHOOSE
backtrack(i + 1, path) # EXPLORE (advance start)
path.pop() # UNCHOOSE
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]Podejście z maską bitową
Alternatywą dla backtrackingu jest maskowanie bitowe: każdy podzbiór odpowiada n-bitowej liczbie, w której bit i równy 1 oznacza uwzględnienie elementu i. Należy iterować od 0 do 2ⁿ - 1 i dla każdej liczby wyodrębnić bity, aby zbudować podzbiór. Jest to podejście iteracyjne, często szybsze w praktyce i bardzo łatwe do zakodowania. Nie uogólnia się jednak równie łatwo na problemy z ograniczeniami (takimi jak limit sumy).
def subsets_bitmask(nums):
n = len(nums)
result = []
for mask in range(1 << n): # 0 to 2^n - 1
subset = []
for i in range(n):
if mask & (1 << i): # bit i is set
subset.append(nums[i])
result.append(subset)
return result
print(subsets_bitmask([1, 2, 3]))
# Same 8 subsets, order may differIteracyjne generowanie podzbiorów
Podejście iteracyjne buduje zbiór potęgowy element po elemencie. Należy rozpocząć od [[] ] (zbioru pustego). Dla każdego nowego elementu trzeba powielić wszystkie istniejące podzbiory, a następnie dodać nowy element do każdej kopii. Po przetworzeniu n elementów wynik zawiera wszystkie 2ⁿ podzbiorów. Jest to równoważne maskowaniu bitowemu, ale bardziej czytelne dla osób niezaznajomionych z operacjami bitowymi.
def subsets_iterative(nums):
result = [[]] # start with empty set
for num in nums:
# For each existing subset, create a new subset with num added
result += [subset + [num] for subset in result]
return result
print(subsets_iterative([1, 2, 3]))
# After num=1: [[], [1]]
# After num=2: [[], [1], [2], [1,2]]
# After num=3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Subsets II: Obsługa duplikatów
Gdy dane wejściowe zawierają duplikaty, naiwne podejście generuje zduplikowane podzbiory. Dla [1, 2, 2] oba wystąpienia wartości 2 niezależnie utworzyłyby [1, 2]. Rozwiązanie polega na wcześniejszym posortowaniu tablicy, a następnie pomijaniu kandydata na bieżącym poziomie, jeśli jest równy poprzedniemu kandydatowi na tym samym poziomie. W pętli należy użyć dokładnie: if i > start and nums[i] == nums[i-1]: continue.
def subsets_with_dups(nums):
nums.sort() # sort to group duplicates together
result = []
def backtrack(start, path):
result.append(list(path))
for i in range(start, len(nums)):
# Skip duplicates at the same tree level
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(subsets_with_dups([1, 2, 2]))
# [[], [1], [1,2], [1,2,2], [2], [2,2]] — no duplicate subsetsDlaczego pomijanie duplikatów działa
Warunek i > start and nums[i] == nums[i-1] pomija duplikat tylko na tym samym poziomie rekurencji (przy tej samej wartości start). Nie uniemożliwia wybrania tej samej wartości na różnych poziomach. Dla [1, 2, 2]: na poziomie 0 dołączamy pierwszą 2 (indeks 1), a następnie na kolejnym poziomie (start=2) dołączamy drugą 2, aby utworzyć [2, 2]. Gdybyśmy jednak spróbowali ponownie dołączyć drugą 2 na poziomie 0, warunek ją wykryje i pominie.
# Visual: [1, 2, 2] sorted
# Level 0 (start=0): pick nothing, pick 1, pick first-2, pick second-2 (SKIP)
# Level 1 after picking 1 (start=1): pick first-2, pick second-2 (SKIP)
# Level 2 after picking 1,first-2 (start=2): pick second-2
# → [1,2,2] is generated but only once
nums = [1, 2, 2]
nums.sort()
result_set = set(tuple(sorted(s)) for s in subsets_with_dups(nums[:]))
result_naive = set(tuple(sorted(s)) for s in subsets(nums))
print('With dedup:', sorted(result_set))
print('Same results:', result_set == result_naive)
def subsets(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
def subsets_with_dups(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]: continue
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
print(len(subsets_with_dups([1,2,2])), 'unique subsets') # 6Podzbiory o ustalonym rozmiarze (k-kombinacje)
Generowanie wyłącznie podzbiorów dokładnie rozmiaru k (LeetCode 77: Combinations) dodaje warunek wczesnego zakończenia: jeśli pozostałe elementy nie mogą uzupełnić ścieżki do rozmiaru k, odcinamy tę gałąź. Warunek umożliwiający przycinanie to i > n - (k - len(path)): jeśli nie zostało wystarczająco dużo elementów, kończymy wcześniej. To znacznie zmniejsza przestrzeń przeszukiwania w porównaniu z generowaniem wszystkich podzbiorów i filtrowaniem wyników.
def combine(n, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(list(path))
return
# Prune: need (k - len(path)) more elements from [start..n]
# At most (n - start + 1) elements remain
if n - start + 1 < k - len(path):
return # not enough elements left
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result
print(combine(4, 2)) # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
print(len(combine(10, 3))) # C(10,3) = 120Zastosowania zbioru potęgowego
Wzorzec zbioru potęgowego pojawia się w wielu wariantach zadań rekrutacyjnych: (1) Podział na dwa równe podzbiory — sprawdzenie, czy jakiś podzbiór ma sumę równą total/2. (2) Maksymalne XOR dwóch podzbiorów — sprawdzenie wszystkich par podzbiorów. (3) Minimalny koszt wybrania k elementów — wyliczenie k-podzbiorów. Chociaż bezpośrednie wyliczanie ma złożoność wykładniczą, wiele z tych problemów można rozwiązać za pomocą DP po rozpoznaniu ich struktury. Ujęcie problemu jako zbioru potęgowego pomaga określić przestrzeń stanów, nawet jeśli zostanie ona później zoptymalizowana.
def max_subset_sum(nums, k):
'''Maximum sum of any k elements (for comparison: O(n log n) alternative)'''
# Backtracking approach: enumerate all k-subsets
max_s = [float('-inf')]
def bt(start, path, curr_sum):
if len(path) == k:
max_s[0] = max(max_s[0], curr_sum)
return
remaining_spots = k - len(path)
for i in range(start, len(nums)):
if len(nums) - i < remaining_spots: break # prune
bt(i+1, path+[nums[i]], curr_sum+nums[i])
bt(0, [], 0)
return max_s[0]
# Much faster: just sort and take top k
def max_subset_sum_fast(nums, k):
return sum(sorted(nums, reverse=True)[:k])
nums = [3, 1, 4, 1, 5, 9, 2, 6]
print(max_subset_sum(nums, 3)) # 20 (9+6+5)
print(max_subset_sum_fast(nums, 3)) # 20Sprawdzanie sumy podzbioru
Subset Sum stawia pytanie: czy istnieje podzbiór tablicy, którego suma jest równa wartości docelowej? Można to rozwiązać za pomocą backtrackingu (wykładniczo) albo DP (wielomianowo). Wersja z backtrackingiem jest prosta, ale dla dużych danych wejściowych staje się niepraktyczna. Wersja DP (boolowska tablica dp[target+1]) jest preferowanym podejściem podczas rozmów kwalifikacyjnych. Zrozumienie obu metod pomaga wyjaśnić kompromis: backtracking zwraca wszystkie rozwiązania, a DP efektywnie rozwiązuje problem decyzyjny.
# Backtracking version: finds a subset if it exists
def subset_sum_bt(nums, target):
def bt(start, remaining):
if remaining == 0: return True
if remaining < 0 or start == len(nums): return False
# Include nums[start]
if bt(start + 1, remaining - nums[start]): return True
# Exclude nums[start]
return bt(start + 1, remaining)
return bt(0, target)
# DP version: O(n * target) time
def subset_sum_dp(nums, target):
dp = {0}
for num in nums:
dp |= {s + num for s in dp}
return target in dp
print(subset_sum_bt([3, 1, 4, 1, 5], 6)) # True (1+5 or 1+1+4)
print(subset_sum_dp([3, 1, 4, 1, 5], 6)) # TrueZłożoność wyliczania podzbiorów
Generowanie wszystkich podzbiorów ma nieuniknioną złożoność czasową O(n × 2ⁿ) — istnieje 2ⁿ podzbiorów, a każdy z nich ma średnio n/2 elementów. Nie da się uzyskać lepszego wyniku, gdy wymagane są wszystkie podzbiory. W problemach, w których trzeba znaleźć jeden podzbiór spełniający określony warunek (np. o maksymalnej sumie), należy preferować DP lub algorytm zachłanny. Kluczowa wskazówka rekrutacyjna: zawsze należy ustalić, czy trzeba wyliczyć wszystkie podzbiory, czy tylko sprawdzić, czy dowolny podzbiór spełnia warunek — od tego zależy, czy dopuszczalna jest złożoność wykładnicza, czy wymagana jest wielomianowa.
import time
def count_subsets(n):
nums = list(range(n))
result = []
def bt(start, path):
result.append(None) # count without storing
for i in range(start, len(nums)):
path.append(i); bt(i+1, path); path.pop()
bt(0, [])
return len(result)
for n in [10, 15, 20]:
start = time.time()
cnt = count_subsets(n)
elapsed = time.time() - start
print(f'n={n}: {cnt} subsets ({2**n} expected) in {elapsed:.3f}s')Porównanie wszystkich trzech podejść
W przypadku generowania wszystkich podzbiorów: Backtracking jest najbardziej uniwersalny — łatwo dostosować go do duplikatów i dodatkowych ograniczeń. Maskowanie bitowe jest zwięzłe i szybkie, ale ograniczone do n ≤ 30 (ze względu na rozmiar liczby całkowitej). Podejście iteracyjne jest intuicyjne i pozwala uniknąć narzutu rekurencji. Wszystkie trzy metody generują dane wyjściowe o rozmiarze O(n × 2ⁿ). Podczas rozmowy kwalifikacyjnej backtracking pokazuje zrozumienie rekurencyjnego procesu podejmowania decyzji, który można uogólnić na trudniejsze problemy. Omawiając podejścia, warto wspomnieć o wszystkich trzech.
# All three approaches for [1,2,3]
nums = [1, 2, 3]
# 1. Backtracking
def bt(start, path, res):
res.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path, res); path.pop()
res1 = []; bt(0, [], res1)
# 2. Bit masking
res2 = [[nums[i] for i in range(len(nums)) if mask & (1<<i)]
for mask in range(1<<len(nums))]
# 3. Iterative
res3 = [[]]
for num in nums:
res3 += [s+[num] for s in res3]
print('All produce', len(nums)**2, '-ish subsets:',
len(res1), len(res2), len(res3)) # all 8Szybki sprawdzian
Proszę sprawdzić swoją znajomość zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że: backtracking generuje wszystkie podzbiory, dodając każdą częściową ścieżkę do wyników przed dalszym przeszukiwaniem, duplikaty obsługuje się przez sortowanie i pomijanie powtarzających się wartości na tej samej głębokości rekurencji za pomocą warunku i > start and nums[i] == nums[i-1], a maskowanie bitowe zapewnia zwięzłą iteracyjną alternatywę, w której każdy podzbiór odpowiada unikatowej masce bitowej. Następnie zajmiemy się permutacjami i kombinacjami — powiązanymi problemami wyliczania, ale z innymi ograniczeniami.
Często zadawane pytania
Czy lekcja „Podzbiory i zbiór potęgowy” jest bezpłatna?
Tak — pełny tekst „Podzbiory i zbiór potęgowy” 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 „Podzbiory i zbiór potęgowy”?
Generować wszystkie podzbiory zbioru za pomocą przeszukiwania z nawrotami i masek bitowych, obsługując duplikaty przez sortowanie i pomijanie powtarzających się elementów Ć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 „Podzbiory i zbiór potęgowy”?
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
- Szablon backtrackingu: wybierz, zbadaj, cofnij wybór
- Podzbiory i zbiór potęgowy
- Permutacje i kombinacje
- Problem N hetmanów i propagacja ograniczeń