Generare tutti i sottoinsiemi
Scegliere o saltare ogni elemento
Generare tutti i sottoinsiemi è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Perché generare i sottoinsiemi
Molti problemi di gara le chiedono di provare ogni sottoinsieme di un insieme piccolo. Con la ricorsione può elencarli in modo chiaro e affidabile. 🧩
Scelga o salti ogni elemento
L'idea fondamentale è questa: per ogni elemento effettua una scelta binaria, includendolo oppure lasciandolo fuori. Ogni insieme completo di scelte produce un sottoinsieme.
Quanti sottoinsiemi esistono
Un insieme di n elementi ha esattamente 2 elevato alla n sottoinsiemi, perché ogni elemento raddoppia il conteggio. Mantenga quindi n piccolo, circa 20 o meno.
Il piano ricorsivo
Attraversi l'array con un indice. A ogni indice crei due rami: uno che include l'elemento e uno che lo salta.
Il caso base
Quando l'indice supera l'ultimo elemento, il percorso corrente è un sottoinsieme completo. Quello è il suo caso base, in cui registrarlo.
La ricorsione dei sottoinsiemi nel codice
Questa esplorazione ricorsiva registra un sottoinsieme alla fine, poi esplora i rami che saltano o includono l'elemento a ogni indice.
def gen(i, cur):
if i == len(a):
out.append(cur[:])
return
gen(i + 1, cur)
gen(i + 1, cur + [a[i]])Faccia backtracking annullando le scelte
Quando aggiunge un elemento, lo rimuova dopo la chiamata ricorsiva affinché il ramo successivo parta pulito. Questo annullamento è il cuore del backtracking.
cur.append(a[i])
gen(i + 1, cur)
cur.pop()L'alternativa della maschera di bit
Può anche associare ogni intero da 0 a (2 elevato alla n) meno 1 a un sottoinsieme, in cui ogni bit indica un elemento incluso.
for mask in range(1 << n):
sub = [a[i] for i in range(n) if mask >> i & 1]Copi prima di salvare
Salvi sempre una copia della lista corrente, non la lista stessa. Altrimenti le modifiche successive sovrascrivono ogni sottoinsieme salvato. ⚠️
Generi combinazioni
Per ottenere sottoinsiemi di dimensione fissa k, interrompa il ramo quando il conteggio degli elementi scelti raggiunge k. Questo trasforma i sottoinsiemi in combinazioni.
Dove compaiono i sottoinsiemi
L'enumerazione dei sottoinsiemi risolve piccoli problemi di zaino, selezione di squadre e verifiche di fattibilità in cui deve testare ogni selezione possibile.
Verifica rapida
Quanti sottoinsiemi ha un insieme di n elementi?
Riepilogo: crei un ramo per ogni elemento
Ha imparato a elencare tutti i sottoinsiemi scegliendo o saltando ogni elemento e annullando la scelta dopo ogni ramo. Mantenga n piccolo, perché il conteggio è 2 elevato alla n. 🎯
Domande Frequenti
La lezione «Generare tutti i sottoinsiemi» è gratuita?
Sì — il testo completo di «Generare tutti i sottoinsiemi» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Generare tutti i sottoinsiemi»?
Scegliere o saltare ogni elemento Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Generare tutti i sottoinsiemi»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Pensare ricorsivamente: caso base e ricorsione
- Generare tutti i sottoinsiemi
- Permutazioni e idea delle N regine
- Potare per superare il limite di tempo