Problème — Parties d'un ensemble

On raisonne sur le premier élément x. Les parties de la liste se répartissent en deux moitiés : celles qui ne contiennent pas x (ce sont les parties du reste) et celles qui le contiennent (les mêmes, augmentées de x). Le cas de base est la liste vide, dont l'unique partie est l'ensemble vide.

def parties(liste):
    if liste == []:
        return [[]]
    x = liste[0]
    sous_parties = parties(liste[1:])
    avec_x = [[x] + p for p in sous_parties]
    return sous_parties + avec_x

print(parties([1, 2, 3]))
# affiche [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Pour un ensemble de $n$ éléments, il existe $2^n$ parties : le coût est nécessairement exponentiel, ce qui est inhérent au problème lui-même.