Wie kann man mit einem rekursiven Ansatz alle möglichen Teilmengen einer Menge mit n Elementen finden?

Alle Teilmengen einer Menge finden

In der Informatik ist das Finden aller Teilmengen einer gegebenen Menge ein klassisches Problem. Die Frage stellt sich wie folgt:

Problem:

Wie bestimmt man alle möglichen Teilmengen einer Menge mit n Elementen?

Lösung:

Ein einfacher Ansatz für dieses Problem liegt in der Rekursion. Das Konzept dreht sich um die Idee, dass:

• Für n=1 sind die Teilmengen {{}, {1}}
• Für n>1 können wir die Teilmengen von dividieren 1,...,n-1 in zwei Gruppen: solche, die n enthalten, und solche, die kein n enthalten. Die Kombination dieser Gruppen ergibt die Teilmengen für 1,...,n.

Beispiel:

Betrachten Sie n=5.

1. Finden Sie die Teilmengen von 1,...,4: {{}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4 }, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}
2. Erstellen Sie eine Kopie und addieren Sie zu jeder 5 Teilmenge: {{5}, {1, 5}, {2, 5}, {3, 5}, {4, 5}, {1, 2, 5}, {1, 3, 5}, {1, 4, 5}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}, {1, 2, 3, 4, 5}}
3. Nehmen Sie die Vereinigung der ursprünglichen und modifizierten Mengen : {{}, {1}, {2}, {3}, {4}, {5}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}, {1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4 , 5}, {1, 3, 4, 5}, {2, 3, 4, 5}, {1, 2, 3, 4, 5}}

C-Implementierung:

#include <vector>

using namespace std;

vector<vector<int>> subsets(vector<int>& nums) {
    if (nums.empty()) return {{}};

    vector<vector<int>> prev = subsets(vector<int>(nums.begin(), nums.end() - 1));
    vector<vector<int>> curr;

    for (auto& subset : prev) {
        curr.push_back(subset);
        subset.push_back(nums.back());
        curr.push_back(subset);
    }

    return curr;
}

Das obige ist der detaillierte Inhalt vonWie kann man mit einem rekursiven Ansatz alle möglichen Teilmengen einer Menge mit n Elementen finden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!