rekursive Funktion Teilmenge in Pseudocode

Hallo,

Ich sitze gerade vor folgender Aufgabe, aber weis leider überhaupt nicht wie ich da anfangen soll
Vielleicht kann mir jemand von euch mit dem Ansatz helfen?

Schreiben Sie eine rekursive Funktion Teilmengen(k,n) in Pseudocode welche die Menge aller k-elementigen Teilmengen der Menge {1, 2, . . . , n} zurück gibt.
Zum Beispiel soll der Funktionsaufruf Teilmengen(3,4) den Rückgabewert { {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4} } liefern.
Erörtern Sie Ihren Algorithmus hinsichtlich der Aspekte Terminierung, Korrektheit und Laufzeit.

Hinweis: Sie dürfen annehmen, dass es einen Datentyp set fur Mengen gibt und dass für zwei Variablen S und T vom Typ set der Ausdruck S + T die Vereinigung dieser Mengen beschreibt.
Achtung: Verwechseln Sie nicht die leere Menge ∅ mit der Menge {∅}, die nur die leere Menge enthält.

icarus2

Als Einstieg kannst du dir vielleicht einmal überlegen wie du alle Teilmengen berechnen kannst (nicht dur die, die genau k Elemente enthalten).

Betrachten wir als Beispiel die Menge $\{1,2,3,4\}$ . Dann nimmst du zuerst die $1$ raus. Diese ist entweder drin oder nicht. Dann betrachtest du nur noch die Teilmenge $\{2,3,4\}$ und führst darauf genau gleiche Rechnung rekursiv aus. Dann musst du dir Überlegen wann die Rekursion abbrechen soll und wie du das ganze zusammensetzt.

PS: Mir ist durchaus bewusst, dass die Erklärung sehr schlecht ist - soll auch so sein. Ich wollte nur einen kleinen Hinweis geben wie die Rekursion aussehen könnte. Die Aufgabe sollst du ja schliesslich selber lösen

Also, ich hab jetzt als Ansatz {n,k} = {n-1,k} + {n-1,k-1}
Macht das Sinn?

icarus2

Keine Ahnung, deine Notation ist komplett unverständlich.

Versuchs einfach mal aufzuschreiben. Falls du es nicht hinbekommst dann google danach. Das ist eine Standardaufgabe zu der man sicher einfach eine Lösung findet.