Generér alle delmængder
Vælg eller spring hvert element over
Generér alle delmængder er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvorfor generere delmængder
Mange konkurrenceopgaver beder dig prøve alle delmængder af et lille sæt. Med rekursion kan du opremse dem enkelt og pålideligt. 🧩
Vælg eller spring hvert element over
Grundideen er, at du for hvert element træffer et binært valg: tag det med, eller lad det være. Hvert komplet sæt valg giver én delmængde.
Hvor mange delmængder findes der
Et sæt med n elementer har præcis 2 i n-te delmængder, fordi hvert element fordobler antallet. Hold derfor n lille, omkring 20 eller mindre.
Den rekursive plan
Før et indeks gennem arrayet. Ved hvert indeks forgrener du dig to gange: én gang, hvor du tager elementet, og én gang, hvor du springer det over.
Basistilfældet
Når indekset passerer det sidste element, er den aktuelle sti én komplet delmængde. Det øjeblik er dit basistilfælde, hvor du gemmer den.
Delmængderekursion i kode
Denne rekursive gennemgang gemmer en delmængde til sidst og undersøger derefter at springe over eller tage elementet ved hvert indeks.
def gen(i, cur):
if i == len(a):
out.append(cur[:])
return
gen(i + 1, cur)
gen(i + 1, cur + [a[i]])Gå tilbage ved at fortryde
Når du føjer et element til, skal du fjerne det efter rekursionen, så den næste gren starter rent. Dette fortrydelsestrin er kernen i tilbageløbssøgning.
cur.append(a[i])
gen(i + 1, cur)
cur.pop()Bitmaskealternativet
Du kan også knytte hvert heltal fra 0 til 2 i n minus 1 til en delmængde, hvor hver bit markerer et element, der er taget med.
for mask in range(1 << n):
sub = [a[i] for i in range(n) if mask >> i & 1]Kopiér, før du gemmer
Gem altid en kopi af den aktuelle liste, ikke selve listen. Ellers overskriver senere ændringer alle de delmængder, du har gemt. ⚠️
Generér kombinationer
Hvis du vil have delmængder med en fast størrelse k, skal du stoppe grenen, når antallet af valgte elementer når k. Så bliver delmængderne til kombinationer.
Hvor delmængder bruges
Oplistning af delmængder løser små rygsækproblemer, holdudvælgelse og gennemførlighedstjek, hvor du skal teste alle mulige valg.
Hurtigt tjek
Hvor mange delmængder har et sæt med n elementer?
Opsummering: Forgren dig ved hvert element
Du har lært at opliste alle delmængder ved at vælge eller springe hvert element over og fortryde efter hver gren. Hold n lille, da antallet er 2 i n-te. 🎯
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Generér alle delmængder” gratis?
Ja — hele teksten til “Generér alle delmængder” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Generér alle delmængder”?
Vælg eller spring hvert element over Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.
Hvor lang tid tager lektionen “Generér alle delmængder”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Tænk rekursivt: base og rekursion
- Generér alle delmængder
- Permutationer og N-Queens-idéen
- Beskær for at overholde tidsgrænsen