Generera alla delmängder
Välj eller hoppa över varje element
Generera alla delmängder är en gratis lektion i Competitive Programming Academy på CoddyKit. Detta är lektion 2 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Competitive Programming Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Varför generera delmängder
Många tävlingsuppgifter ber dig prova varje delmängd av en liten mängd. Med rekursion kan du lista alla på ett tydligt och tillförlitligt sätt. 🧩
Välj eller hoppa över varje element
Grundidén är att göra ett binärt val för varje element: ta med det eller lämna det. Varje komplett uppsättning val ger en delmängd.
Hur många delmängder finns det
En mängd med n element har exakt 2 upphöjt till n delmängder, eftersom varje element fördubblar antalet. Håll därför n litet, omkring 20 eller mindre.
Den rekursiva planen
Låt ett index gå genom arrayen. Vid varje index förgrenar du dig på två sätt: en gång genom att ta elementet och en gång genom att hoppa över det.
Basfallet
När indexet har passerat det sista elementet är den aktuella vägen en komplett delmängd. Då har du nått ditt basfall och ska spara den.
Delmängdsrekursion i kod
Den här rekursiva genomgången sparar en delmängd i slutet och utforskar sedan att hoppa över eller ta elementet vid varje index.
def gen(i, cur):
if i == len(a):
out.append(cur[:])
return
gen(i + 1, cur)
gen(i + 1, cur + [a[i]])Backtracka genom att ångra
När du lägger till ett element tar du bort det efter rekursionen så att nästa gren börjar med en ren lista. Det steget att ångra är kärnan i backtracking.
cur.append(a[i])
gen(i + 1, cur)
cur.pop()Bitmaskalternativet
Du kan också koppla varje heltal från 0 till 2 upphöjt till n minus 1 till en delmängd, där varje bit markerar ett inkluderat element.
for mask in range(1 << n):
sub = [a[i] for i in range(n) if mask >> i & 1]Kopiera innan du sparar
Spara alltid en kopia av den aktuella listan, inte själva listan. Annars skriver senare ändringar över varje delmängd som du sparat. ⚠️
Generera kombinationer
Om du vill ha delmängder av en bestämd storlek k avslutar du grenen när antalet valda element når k. Då blir delmängderna kombinationer.
Där delmängder används
Att enumerera delmängder löser små ryggsäcksproblem, laguttagningar och genomförbarhetskontroller där du måste testa varje möjligt urval.
Snabb kontroll
Hur många delmängder har en mängd med n element?
Repetition: förgrena dig vid varje element
Du har lärt dig att lista alla delmängder genom att välja eller hoppa över varje element och ångra efter varje gren. Håll n litet eftersom antalet är 2 upphöjt till n. 🎯
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Generera alla delmängder” gratis?
Ja – hela texten till ”Generera alla delmängder” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Competitive Programming Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Vad lär jag mig i ”Generera alla delmängder”?
Välj eller hoppa över varje element Ni övar på Competitive Programming Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Competitive Programming Academy?
Du behöver inga förkunskaper. Utbildningen i Competitive Programming Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 2 av 4.
Hur lång tid tar lektionen ”Generera alla delmängder”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Competitive Programming Academy-lektionen?
Ja. Varje Competitive Programming Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Tänk rekursivt: basfall och rekursion
- Generera alla delmängder
- Permutationer och idén bakom N-damer
- Beskär sökningen för att klara tidsgränsen