Générer tous les sous-ensembles
Choisir ou ignorer chaque élément
Générer tous les sous-ensembles est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Pourquoi générer des sous-ensembles
De nombreux problèmes de concours vous demandent d'essayer chaque sous-ensemble d'un petit ensemble. Avec la récursivité, vous pouvez tous les énumérer clairement et de manière fiable. 🧩
Choisissez ou ignorez chaque élément
L'idée centrale : pour chaque élément, vous faites un choix binaire, soit vous l'incluez, soit vous le laissez de côté. Chaque ensemble complet de choix produit un sous-ensemble.
Combien existe-t-il de sous-ensembles
Un ensemble de n éléments contient exactement 2 puissance n sous-ensembles, car chaque élément double le nombre total. Gardez donc n petit, autour de 20 ou moins.
Le plan récursif
Faites avancer un indice dans le tableau. À chaque indice, créez deux branches : l'une prend l'élément, l'autre l'ignore.
Le cas de base
Lorsque l'indice dépasse le dernier élément, le chemin courant constitue un sous-ensemble complet. C'est le moment qui forme votre cas de base pour l'enregistrer.
La récursivité des sous-ensembles en code
Ce parcours récursif enregistre un sous-ensemble à la fin, puis explore les choix consistant à ignorer ou à prendre l'élément de chaque indice.
def gen(i, cur):
if i == len(a):
out.append(cur[:])
return
gen(i + 1, cur)
gen(i + 1, cur + [a[i]])Revenez en arrière en annulant
Lorsque vous utilisez append pour ajouter un élément, retirez-le après l'appel récursif afin que la branche suivante démarre dans un état propre. Cette annulation est au cœur du retour sur trace.
cur.append(a[i])
gen(i + 1, cur)
cur.pop()L'alternative du masque binaire
Vous pouvez aussi associer chaque entier de 0 à 2 puissance n moins 1 à un sous-ensemble : chaque bit indique si un élément est inclus.
for mask in range(1 << n):
sub = [a[i] for i in range(n) if mask >> i & 1]Copiez avant d'enregistrer
Enregistrez toujours une copie de la liste courante, et non la liste elle-même. Sinon, les modifications ultérieures écraseront chaque sous-ensemble enregistré. ⚠️
Générer des combinaisons
Pour obtenir des sous-ensembles de taille fixe k, arrêtez la branche dès que le compte des éléments choisis atteint k. Vous transformez ainsi les sous-ensembles en combinations.
Où apparaissent les sous-ensembles
L'énumération des sous-ensembles permet de résoudre de petits problèmes de sac à dos, de sélection d'équipes et de vérification de faisabilité lorsque vous devez tester chaque sélection possible.
Vérification rapide
Combien de sous-ensembles possède un ensemble de n éléments ?
Récapitulatif : une branche pour chaque élément
Vous avez appris à énumérer tous les sous-ensembles en choisissant ou en ignorant chaque élément, puis en annulant le choix après chaque branche. Gardez n petit, car le nombre vaut 2 puissance n. 🎯
Questions Fréquemment Posées
La leçon « Générer tous les sous-ensembles » est-elle gratuite ?
Oui — le texte complet de « Générer tous les sous-ensembles » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Générer tous les sous-ensembles » ?
Choisir ou ignorer chaque élément Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Générer tous les sous-ensembles » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Raisonner récursivement : base et récursion
- Générer tous les sous-ensembles
- Permutations et idée des N reines
- Élaguer pour respecter la limite de temps