Subsets

Ordne die sortierten Werte den Positionen 0 bis n-1 zu. Eine Teilmenge gibt für jede Position an, ob sie enthalten ist oder nicht, und genau das leisten die n Bits einer Zahl. Die Zahlen von 0 bis 2^n-1 stehen also für die Teilmengen: Für [1, 2, 3] ist die Maske 5 binär 101, die Bits 0 und 2 sind gesetzt und stehen für [1, 3]. Maske 0 ist die leere Teilmenge und Maske 7 ist die vollständige Liste.

Verschiedene Masken ergeben verschiedene Teilmengen und jede Teilmenge hat eine Maske, also erzeugt die Schleife alle 2^n Teilmengen genau einmal. Wenn man die Bits von Position 0 aufwärts anhand der sortierten Werte ausliest, wird jede Teilmenge in aufsteigender Reihenfolge geschrieben.

Die Masken kommen nicht in der vom Problem verlangten Reihenfolge heraus. Maske 1 ist [1], Maske 2 ist [2] und Maske 3 ist [1, 2], also würde [2] vor [1, 2] landen. Das behebst du mit einer Sortierung, deren Vergleichsfunktion die Werte der Reihe nach vergleicht und ein Präfix zuerst einordnet. Die Sortierung kostet mehr als die Erzeugung: Für 2^n Teilmengen braucht man ungefähr n × 2^n Vergleiche, und jeder Vergleich liest bis zu n Werte. Für n = 10 sind das etwa 10^5 Lesezugriffe, immer noch schnell, aber ein Aufwand, den der nächste Ansatz gar nicht erst hat.

Stell dir die Teilmengen als Baum vor. Die Wurzel ist die leere Teilmenge. Unterhalb eines Knotens kannst du jeden Wert hinzufügen, der größer ist als der zuletzt hinzugefügte. Für sortierte Werte [1, 2, 3] hat die Wurzel die Kinder [1], [2] und [3]; [1] hat die Kinder [1, 2] und [1, 3]; [1, 2] hat das Kind [1, 2, 3]. Jede Teilmenge kommt in diesem Baum genau einmal vor, denn es gibt nur eine Möglichkeit, sie in aufsteigender Reihenfolge zu schreiben, und jeder Knoten ist eine Lösung, nicht nur die Blätter.

Beim Backtracking wird der Baum mit einer gemeinsamen Liste path durchlaufen. Um zu einem Kind hinabzusteigen, wählst du: Füge den Wert hinzu. Du erkundest den Zweig: Rufe die Funktion rekursiv auf, und der Helfer speichert eine Kopie von path, sobald er dort ankommt. Dann machst du die Wahl rückgängig: Entferne den Wert, sodass path wieder beim Elternknoten ist und das nächste Geschwisterelement ausprobiert werden kann. Da jeder Knoten beim Betreten aufgezeichnet wird, wird ein Elternknoten immer vor seinen Kindern ausgegeben.

Deshalb ist die Ausgabe ohne Sortierung in lexikografischer Reihenfolge. Die Kinder eines Knotens werden vom kleinsten Wert an ausprobiert, und der Durchlauf beendet einen ganzen Zweig, bevor er mit dem nächsten beginnt. Für [1, 2, 3] werden [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3] aufgezeichnet: die Reihenfolge eines Wörterbuchs, wobei ein Präfix vor seinen Erweiterungen steht.

Der Baum hat 2^n Knoten, und das Kopieren eines Pfads kostet bis zu n, daher beträgt die Laufzeit O(n × 2^n), also die Größe der Antwort selbst. Zusätzlich zur Ausgabe benötigst du einen Pfad und einen Aufrufstapel, die beide höchstens n tief sind.