Delmengder og potensmengde
Generer alle delmengder av en mengde ved hjelp av tilbakesporing og bitmaskering, og håndter duplikater ved å sortere og hoppe over gjentatte elementer.
Delmengder og potensmengde er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Delmengder og potensmengden
Potensmengden til en mengde S er samlingen av alle mulige delmengder av S, inkludert den tomme mengden og S selv. En mengde med n elementer har nøyaktig 2ⁿ delmengder. For [1, 2, 3] er de 8 delmengdene: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. Dette er et grunnleggende kombinatorisk problem som dukker opp i intervjuspørsmål om å finne alle mulige kombinasjoner, partisjoneringer eller valg.
# 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: 16Generering av delmengder med backtracking
Bruk malen Velg–utforsk–angre valg. Den viktigste designbeslutningen er at den gjeldende delvise stien legges til i resultatene umiddelbart ved hvert rekursive kall, før flere elementer velges. På denne måten registreres hver tilstand — tom, delvis og fullstendig — som en gyldig delmengde. Flytt start-indeksen fremover slik at bare elementer til høyre for det sist valgte elementet vurderes. Dermed unngås duplikater, og rekkefølgen bevares.
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]]Tilnærming med bitmaskering
Et alternativ til backtracking er bitmaskering: hver delmengde svarer til et n-bits tall der bit i med verdien 1 betyr at element i er inkludert. Iterer fra 0 til 2ⁿ - 1, og hent ut bitene for hvert tall for å bygge delmengden. Dette er iterativt, ofte raskere i praksis og svært enkelt å implementere. Det generaliserer imidlertid ikke like ryddig til problemer med begrensninger, for eksempel en sumgrense.
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 differIterativ generering av delmengder
Den iterative tilnærmingen bygger opp potensmengden element for element. Start med [[] ] (den tomme mengden). For hvert nye element dupliseres alle eksisterende delmengder, og det nye elementet legges til hver kopi. Etter at n elementer er behandlet, inneholder resultatet alle 2ⁿ delmengder. Dette tilsvarer bitmaskering, men er mer lesbart for dem som ikke kjenner bitvise operasjoner.
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: Håndtering av duplikater
Når inndataene inneholder duplikater, genererer den naive tilnærmingen dupliserte delmengder. For [1, 2, 2] ville begge forekomstene av 2 uavhengig generert [1, 2]. Løsning: sorter arrayet først, og hopp over en kandidat på det aktuelle nivået hvis den er lik den forrige kandidaten på samme nivå. I løkken gjelder spesielt: 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 subsetsHvorfor det fungerer å hoppe over duplikater
Betingelsen i > start and nums[i] == nums[i-1] hopper over et duplikat bare på samme rekursjonsnivå (samme start). Den hindrer ikke at samme verdi velges på ulike dybder. For [1, 2, 2]: På nivå 0 inkluderer vi den første 2-en (indeks 1), og på neste nivå (start=2) inkluderer vi den andre 2-en for å danne [2, 2]. Men hvis vi prøvde å inkludere den andre 2-en på nivå 0 igjen, oppdager betingelsen dette og hopper over den.
# 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') # 6Delmengder med fast størrelse (k-kombinasjoner)
Å generere bare delmengder med nøyaktig størrelse k (LeetCode 77: Combinations) legger til en tidlig avslutningsbetingelse: Hvis de gjenværende elementene ikke kan fylle stien opp til størrelse k, beskjærer vi søket. Beskjæringsbetingelsen er i > n - (k - len(path)): Hvis det ikke er nok elementer igjen, avslutter vi tidlig. Dette reduserer søkerommet betydelig sammenlignet med å generere alle delmengder og filtrere dem etterpå.
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) = 120Anvendelser av potensmengder
Mønsteret for potensmengder dukker opp i mange varianter av intervjuspørsmål: (1) Dele opp i to like delmengder — sjekk om en delmengde har sum lik totalen/2. (2) Maksimal XOR av to delmengder — prøv alle par av delmengder. (3) Minste kostnad ved å velge k elementer — enumerer k-del mengder. Selv om direkte enumerering er eksponentiell, kan mange av disse problemene løses med DP når du først gjenkjenner strukturen. Perspektivet med potensmengder hjelper deg med å identifisere tilstandsrommet, selv når du senere optimaliserer løsningen.
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)) # 20Kontroll av delmengdesum
Subset Sum spør: Har en delmengde av arrayet sum lik et mål? Dette kan løses med backtracking (eksponentiell tid) eller DP (polynomisk tid). Backtracking-versjonen er enkel, men blir upraktisk for store inndata. DP-versjonen (den boolske tabellen dp[target+1]) er den foretrukne tilnærmingen i intervjuer. Når du forstår begge, kan du forklare avveiningen: Backtracking finner alle løsningene, mens DP effektivt besvarer avgjørelsesproblemet.
# 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)) # TrueKompleksiteten ved å generere delmengder
Generering av alle delmengder har en uunngåelig tidskompleksitet på O(n × 2ⁿ) — 2ⁿ delmengder, hver med en gjennomsnittlig størrelse på n/2. Ingen algoritme kan gjøre dette raskere når alle delmengder skal returneres. For problemer som ber om én delmengde med en bestemt egenskap (for eksempel maksimal sum), bør DP eller en grådig algoritme foretrekkes. Viktig innsikt fra intervjuer: Spør alltid om du må enumerere alle delmengder, eller bare finne ut om en eller annen delmengde oppfyller en betingelse — svaret avgjør om eksponentiell eller polynomisk tid er akseptabelt.
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')Sammenligning av alle tre metodene
For å generere alle delmengder er backtracking den mest generaliserbare metoden — den kan enkelt tilpasses duplikater og begrensninger. Bitmaskering er kortfattet og rask, men begrenset til n ≤ 30 (heltallsstørrelse). Iterativ generering er intuitiv og unngår rekursjonskostnaden. Alle tre produserer utdata med størrelsen O(n × 2ⁿ). I et intervju viser backtracking at du forstår den rekursive beslutningsprosessen, som kan generaliseres til vanskeligere problemer. Nevn alle tre når du diskuterer ulike tilnærminger.
# 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 8Kjapp kontroll
Test forståelsen din av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte du at backtracking genererer alle delmengder ved å legge hver delvise sti til resultatene før den utforsker videre, at duplikater håndteres ved å sortere og hoppe over gjentatte verdier på samme rekursjonsdybde med betingelsen i > start and nums[i] == nums[i-1], og at bitmaskering gir et kortfattet iterativt alternativ der hver delmengde tilordnes en unik bitmaske. Neste gang tar vi for oss permutasjoner og kombinasjoner — relaterte enumereringsproblemer med andre begrensninger.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Delmengder og potensmengde» gratis?
Ja – hele teksten i «Delmengder og potensmengde» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Delmengder og potensmengde»?
Generer alle delmengder av en mengde ved hjelp av tilbakesporing og bitmaskering, og håndter duplikater ved å sortere og hoppe over gjentatte elementer. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.
Hvor lang tid tar leksjonen «Delmengder og potensmengde»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Mal for backtracking: velg, utforsk, velg bort
- Delmengder og potensmengde
- Permutasjoner og kombinasjoner
- N-dronninger og begrensningspropagering