Les sous-listes d'une somme donnée

def sommes_possibles(t: list, cible: float) -> list:
    if t == []:
        return [[]] if cible == 0 else []
    sans = sommes_possibles(t[1:], cible)
    avec = [[t[0]] + s for s in sommes_possibles(t[1:], cible - t[0])]
    return sans + avec

def existe_somme(t: list, cible: float) -> bool:
    if t == []:
        return cible == 0
    return (existe_somme(t[1:], cible)
            or existe_somme(t[1:], cible - t[0]))

La version booléenne tire profit du court-circuit de l'opérateur or : dès qu'un chemin renvoie True, les autres branches de l'arbre combinatoire ne sont pas explorées. La complexité dans le pire des cas reste toutefois exponentielle en $O(2^n)$.