Comment trouver tous les sous-ensembles possibles d'un ensemble de n éléments en utilisant une approche récursive ?

Rechercher tous les sous-ensembles d'un ensemble

En informatique, trouver tous les sous-ensembles d'un ensemble donné est un problème classique. La question se pose comme suit :

Problème :

Comment déterminer tous les sous-ensembles possibles d'un ensemble à n éléments ?

Solution :

Une approche simple de ce problème réside dans la récursivité. Le concept tourne autour de l'idée que :

• Pour n=1, les sous-ensembles sont {{}, {1}}
• Pour n>1, nous pouvons diviser les sous-ensembles de 1,...,n-1 en deux groupes : ceux contenant n et ceux ne contenant pas n. La combinaison de ces groupes donne les sous-ensembles pour 1,...,n.

Exemple :

Considérons n=5.

1. Trouvez les sous-ensembles de 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. Créez une copie et ajoutez 5 à chacune sous-ensemble : {{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. Prendre l'union des ensembles originaux et modifiés : {{}, {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}}

Implémentation C :

#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;
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!