Aller au contenu principal

Somme de sous-ensemble par retour sur trace

Le problème de décision de la somme de sous-ensemble 0/1 demande s'il existe un sous-ensemble des éléments donnés dont la somme atteint une cible. Chaque position d'entrée peut être sélectionnée au plus une fois. Énumérer toutes les solutions concrètes constitue un problème de sortie plus vaste que décider de leur existence.

Pour des entiers positifs, le tri autorise un élagage utile :

def subset_sum_witnesses(values: list[int], target: int) -> list[list[int]]:
    values = sorted(values)
    result: list[list[int]] = []
    path: list[int] = []

    def visit(start: int, remaining: int) -> None:
        if remaining == 0:
            result.append(path.copy())
            return
        for i in range(start, len(values)):
            if i > start and values[i] == values[i - 1]:
                continue
            if values[i] > remaining:
                break
            path.append(values[i])
            visit(i + 1, remaining - values[i])
            path.pop()

    visit(0, target)
    return result

L'indice start croissant impose l'utilisation 0/1 et un ordre canonique. Ignorer les valeurs égales à une même profondeur supprime les multi-ensembles de valeurs en double.

Limites​

  • L'élagage value > remaining n'est sûr que sous l'hypothèse de valeurs positives ; des valeurs négatives l'invalident.
  • Passer i plutôt que i + 1 transforme le problème en une réutilisation illimitée.
  • Générer les permutations d'un sous-ensemble n'est pas le problème de la somme de sous-ensemble ; l'ordre ne doit pas créer de nouvelle solution.

Dans le pire cas, la recherche explore 2n2^n sous-ensembles. Pour des cibles entières non négatives, un programme dynamique limité à la décision s'exécute en temps pseudo-polynomial O(nT)O(nT), où TT est la cible, en échangeant la grandeur numérique contre le nombre d'états.

Trace des solutions et coût de sortie​

Pour [1,1,2,3] et la cible 4, choisir 1 laisse 3. Choisir ensuite le second 1 laisse 2 et trouve [1,1,2] ; choisir plutôt 3 trouve [1,3]. Le second 1 à la racine est ignoré, car il répéterait les mêmes multi-ensembles. La branche commençant par 2 ne peut se compléter avec le 3 restant et est élaguée. La sortie complète est donc [[1,1,2],[1,3]].

Avec des entiers positifs, une cible nulle possède exactement la solution vide [[]] ; une cible négative n'en possède aucune. L'entrée vide suit la même règle. Les zéros sortent du contrat : retourner dès que le reste est nul manquerait [0] et d'autres extensions. Les valeurs négatives invalident aussi le retour anticipé et l'élagage : [-3,-2] peut totaliser −5 alors que sa première valeur triée dépasse déjà la cible. Pour des valeurs signées, utilisez une récursion inclusion/exclusion sur les positions et testez la somme à la fin, ou démontrez des bornes adaptées aux signes.

L'indice croissant borne la profondeur par n. L'état auxiliaire, copie triée et pile comprises, coûte O(n) ; conserver et copier les solutions ajoute jusqu'à O(n·2ⁿ) en temps et en espace de sortie au pire. Le programme de décision O(nT) suppose des valeurs d'éléments entières non négatives, et pas seulement une cible non négative.

assert subset_sum_witnesses([1, 1, 2, 3], 4) == [[1, 1, 2], [1, 3]]
assert subset_sum_witnesses([], 0) == [[]]
assert subset_sum_witnesses([], 1) == []

Source​

Explorer les liens

Citée par (1)

Sur les mêmes sujets (35)

Ouvrir le réseau