Teilmenge mit Bitmasken aufzählen
Durchlaufen Sie alle Teilmengen mithilfe von Ganzzahlen
Teilmenge mit Bitmasken aufzählen ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Teilmengen als Zahlen
Jede Teilmenge von n Elementen lässt sich einer einzelnen Ganzzahl zuordnen. Zählen Sie ab 0 aufwärts, und die Bits jeder Zahl bestimmen genau, welche Elemente enthalten sind. 🙂
Wie viele Teilmengen gibt es
Eine Menge aus n Elementen hat 2^n Teilmengen. Wenn Sie daher eine ganze Zahl von 0 bis 2^n minus 1 durchlaufen, besuchen Sie jede Teilmenge genau einmal.
for mask in range(1 << n):
pass # mask is one subset1 << n ist die Anzahl
Der Shift 1 << n entspricht 2 hoch n. So schreiben Sie die obere Grenze Ihrer Teilmengenschleife klar und effizient.
Bit i auslesen
Um zu prüfen, ob Element i in der Teilmenge enthalten ist, testen Sie sein Bit mit mask und einer um i nach links verschobenen 1. Ein Ergebnis ungleich null bedeutet, dass es enthalten ist.
if mask & (1 << i):
take(items[i])Ausgewählte Liste erstellen
Gehen Sie jede Bitposition durch und sammeln Sie die Elemente, deren Bit gesetzt ist. So wird aus einer Maske die konkrete Teilmenge, die sie darstellt.
chosen = [items[i] for i in range(n) if mask & (1 << i)]Leere und vollständige Mengen
Maske 0 ist die leere Teilmenge, und die Maske aus lauter Einsen ist die vollständige Menge. Beide erhalten Sie automatisch, da Ihre Schleife jeden Wert abdeckt.
Über eine Teilmenge summieren
Addieren Sie innerhalb der Schleife die ausgewählten Elemente, um jede Teilmenge zu bewerten. Das ist der Kern vieler kleiner Brute-Force-Lösungen.
total = sum(v[i] for i in range(n) if mask & (1 << i))Gesetzte Bits zählen
Die Anzahl der ausgewählten Elemente entspricht dem popcount der Maske. In Python liefert bin(mask).count('1') diesen Wert sofort.
size = bin(mask).count("1")Die Grenze beachten
Da es 2^n Teilmengen gibt, eignet sich diese Technik nur für kleine Werte von n. Bei ungefähr n gleich 20 liegt die praktische Grenze für eine vollständige Aufzählung.
Warum Bitmasken überzeugen
Eine Schleife über eine ganze Zahl ersetzt unübersichtliche verschachtelte Schleifen, und Bitoperationen sind schnell. Der Code bleibt kurz, übersichtlich und leicht zu testen.
Ein wiederverwendbares Muster
Durchlaufen Sie mask, dekodieren Sie die Bits, bewerten Sie die Teilmenge und speichern Sie das beste Ergebnis. Prägen Sie sich dieses Muster ein, dann werden viele Teilmengenprobleme zur Routine.
Kurzprüfung
Sie möchten prüfen, ob Element i in der durch mask codierten Teilmenge enthalten ist.
Zusammenfassung
Durchlaufen Sie eine mask von 0 bis 2^n minus 1, lesen Sie Bits mithilfe von mask und einer nach links verschobenen 1 aus und bewerten Sie jede Teilmenge. Das ist eine klare Brute-Force-Methode für kleine Werte von n. 🚀
Häufig gestellte Fragen
Ist die Lektion „Teilmenge mit Bitmasken aufzählen“ kostenlos?
Ja — der vollständige Text von „Teilmenge mit Bitmasken aufzählen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Teilmenge mit Bitmasken aufzählen“?
Durchlaufen Sie alle Teilmengen mithilfe von Ganzzahlen Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Teilmenge mit Bitmasken aufzählen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Brute Force ist eine gültige Strategie
- Mit itertools aufzählen
- Teilmenge mit Bitmasken aufzählen
- Den Suchraum gezielt verkleinern