Comment trouver tous les sous-ensembles d'un ensemble en utilisant une approche récursive ?

Recherche de tous les sous-ensembles d'un ensemble

Étant donné un ensemble de n éléments, un sous-ensemble est toute combinaison de ces éléments. L'objectif est de trouver un algorithme complet qui génère tous les sous-ensembles possibles.

Solution récursive

Considérez l'algorithme suivant :

• Cas de base : Si l'ensemble ne contient qu'un seul élément, l'algorithme renvoie un ensemble vide et un ensemble contenant cet élément.
• Étape récursive : Pour un ensemble de n éléments, recherchez l'ensemble des sous-ensembles des n-1 premiers éléments.
• Split : Divisez l'ensemble précédent en deux groupes : les sous-ensembles qui contiennent le nième élément et les sous-ensembles qui ne le contiennent pas.
• Union : Prenez l'union de ces deux groupes pour former l'ensemble complet de sous-ensembles.

Exemple : {1,2,3,4,5}

Étape 1 : Recherchez tous les sous-ensembles de {1,2,3,4}. Ce sont : {}, {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} et {1,2,3,4} .

Étape 2 : Ajoutez 5 à chaque sous-ensemble de l'étape 1 et union avec les sous-ensembles :

• {} -> {}
• {1} -> {1} et {1,5}
• {2} -> {2} et {2,5}
• ...
• {1,2,3,4} -> {1,2,3,4} et {1,2,3,4,5}

L'union de ces sous-ensembles nous donne l'ensemble complet des sous-ensembles pour {1,2,3, 4,5} :

{ {}, {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} et {1,2,3,4,5} }

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!