Combination Sum

Q: Pourquoi appelez-vous récursivement avec i et non i + 1 dans Combination Sum ?

La récursion avec i permet de reprendre la même valeur candidate, ce qui permet d’utiliser une valeur plusieurs fois. La récursion avec i + 1 la dépasse, ce qui transforme le problème en une variante où chaque candidate est utilisée au plus une fois. L’autre moitié de la règle est tout aussi importante : ne jamais revenir à un indice antérieur à i maintient chaque combinaison en ordre croissant et évite les doublons.

MoyenRetour sur trace

+10

Vous disposez d’une liste candidates d’entiers positifs différents et d’un entier positif target. Trouvez toutes les combinaisons de candidats dont les valeurs donnent exactement target, chaque candidat pouvant être utilisé autant de fois que vous le souhaitez. Deux combinaisons sont identiques lorsqu’elles utilisent les mêmes valeurs le même nombre de fois : [2, 3, 3] et [3, 2, 3] ne comptent donc qu’une seule fois.

Renvoyez chaque combinaison avec ses valeurs en ordre croissant, et les combinaisons en ordre lexicographique : comparez deux combinaisons valeur par valeur de gauche à droite ; celle qui a la plus petite valeur à la première différence vient en premier.

Fonction

combinationSum(candidates: integer-array, target: integer) → integer-2d-array

candidatesinteger-array: les différentes valeurs que vous pouvez utiliser, dans n’importe quel ordre, autant de fois que vous le souhaitez
targetinteger: le total de chaque combinaison doit être exactement égal
Renvoieinteger-2d-array: toutes les combinaisons dont la somme est égale à la cible, chacune en ordre croissant, classées par ordre lexicographique

Contraintes

1 ≤ candidates.length ≤ 50
2 ≤ candidates[i] ≤ 500
2 ≤ target ≤ 500
Toutes les valeurs de candidates sont différentes, sans ordre particulier.
Au moins une combinaison atteint target, et au plus 150 y parviennent.

Exemples

Entrée: candidates = [6, 2, 3]target = 8
Sortie: [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
Explication: Quatre 2 font 8, tout comme 2 + 3 + 3 et 2 + 6. Les trois commencent par 2, donc la deuxième valeur détermine l’ordre : 2, puis 3, puis 6. Sans 2, il ne reste que des 3 et des 6, et tous leurs mélanges sont des multiples de 3, ce que 8 n’est pas.

Entrée: candidates = [5, 3, 4]target = 11
Sortie: [[3, 3, 5], [3, 4, 4]]
Explication: 3 + 3 + 5 et 3 + 4 + 4 font tous deux 11. Ils correspondent à la première valeur, et pour la deuxième, le 3 est inférieur au 4, donc [3, 3, 5] vient en premier. Aucun mélange de 4 et de 5 uniquement ne donne 11.

Entrée: candidates = [4, 9]target = 9
Sortie: [[9]]
Explication: 9 tout seul est une combinaison. Les 4 ne donnent que 4, 8 et 12 en passant par 9, et 4 + 9 font déjà 13, donc [9] est la seule réponse.

+12 tests cachés à la soumission

Pour aller plus loin

Chaque candidat ne peut désormais être utilisé qu'une seule fois, et candidates peut contenir des valeurs répétées. Comment modifier la recherche pour qu'aucune combinaison n'apparaisse deux fois ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Chaque réponse est un multiensemble de candidats, et le piège consiste à construire plusieurs fois le même multiensemble : choisir 2, puis 3, puis 3, et choisir 3, puis 2, puis 3 mènent à la même combinaison. L’idée qui permet de résoudre le problème est de construire chaque combinaison dans l’ordre croissant, de sorte qu’il n’existe qu’une seule façon de la construire, et de trier les candidats afin qu’une branche s’arrête dès que la valeur suivante est supérieure à ce qu’il reste. Ce même parcours dans l’ordre croissant fournit les combinaisons dans l’ordre lexicographique, sans tri final.

Essayez chaque nombre pour chaque candidat

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Une combinaison est entièrement décrite par le nombre de fois où elle utilise chaque candidat. Pour [6, 2, 3] et une cible de 8, la réponse [2, 3, 3] contient un 2, deux 3 et aucun 6. Ainsi, une façon de trouver toutes les réponses consiste à essayer chaque nombre possible pour chaque candidat et à conserver les choix dont le total est exactement égal à target. Un candidat c peut être utilisé au plus target / c fois ; son nombre d’occurrences va donc de 0 à cette limite.

Imagine un arbre de décision avec un niveau par candidat, après les avoir triés. Au niveau i, tu décides combien d’exemplaires de la i-ème valeur prendre, et chaque feuille tout en bas correspond à un choix complet de nombres d’occurrences. Chaque multiensemble correspond à une seule liste de nombres d’occurrences, donc aucune combinaison n’est trouvée deux fois. Essayer d’abord le nombre le plus élevé donne aussi l’ordre demandé : lorsque deux réponses diffèrent pour la première fois par le nombre d’occurrences d’une valeur, celle qui en contient davantage conserve cette petite valeur, tandis que l’autre contient déjà une valeur plus grande ; elle vient donc en premier.

Le problème est la taille de l’arbre. Le nombre de feuilles est le produit de target / c + 1 pour tous les candidats : pour [2, 3, 6] trié et une cible de 8, cela donne 5 × 3 × 2 = 30 feuilles pour 3 réponses. Chaque candidat supérieur à target / 2 double le nombre de feuilles, même s’il ne peut être utilisé qu’une seule fois ; ainsi, 40 candidats de ce type suffisent à produire 2^40, soit environ 10^12 feuilles. Les grands tests sont conçus de cette manière, et cette approche ne peut pas les terminer.

Algorithme

Triez les candidats et créez un tableau de comptes, un par valeur.
Écrivez choose(i, total), qui fixe le compte de la valeur à l’index i.
Pour k, de target / nums[i] jusqu’à 0, définissez le compte à k et appelez choose(i + 1, total + k × nums[i]).
Lorsque chaque valeur a un compte, conservez la combinaison si total est égal à target, en écrivant chaque valeur autant de fois que son compte.
Appelez choose(0, 0). Les combinaisons conservées sont déjà dans l’ordre lexicographique.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    counts = [0] * len(nums)
    result = []

    def choose(i, total):
        if i == len(nums):
            if total == target:
                combo = []
                for value, k in zip(nums, counts):
                    combo.extend([value] * k)
                result.append(combo)
            return
        # Most copies first, so the combinations come out in lexicographic order.
        for k in range(target // nums[i], -1, -1):
            counts[i] = k
            choose(i + 1, total + k * nums[i])
        counts[i] = 0

    choose(0, 0)
    return result

Revenir en arrière dans l’ordre croissant et élaguer

Intuition

Construisez chaque combinaison valeur par valeur, comme vous l’écririez : dans l’ordre croissant. L’indice de départ impose cet ordre. Après avoir placé nums[i], la valeur suivante peut être à nouveau nums[i], car un candidat peut se répéter, ou n’importe quelle valeur ultérieure, mais jamais une valeur précédente. L’appel qui a placé l’indice i parcourt donc uniquement les indices de i à la fin. Chaque combinaison n’a qu’un seul ordre croissant, donc un seul chemin dans l’arbre, et un doublon tel que [3, 2, 3] n’est jamais construit.

Voici l’arbre complet pour [2, 3, 6] trié et la cible 8. La racine a 8 comme reste et essaie 2, 3 et 6. Sous 2, il reste 6. Sous 2, 2, il reste 4, et après 2, 2, 2, il reste 2 ; un 2 de plus donne la réponse [2, 2, 2, 2] ; 2, 2, 3 laisse 1 et mène à une impasse. Sous 2, 3, il reste 3 et on ne peut essayer que 3 et 6 ; le 3 donne [2, 3, 3]. Sous 2, 6, il ne reste rien : [2, 6]. Sous 3, on ne peut essayer que 3 et 6, et 3, 3 laisse 2, ce qui ne permet pas de compléter la somme. Sous 6, il reste 2 et on ne peut essayer que 6. Douze appels au total, contre les 30 feuilles de la première approche.

Le tri transforme une impasse en arrêt anticipé. Lorsque nums[i] est supérieur à ce qu’il reste, toutes les valeurs suivantes sont également supérieures ; on quitte donc la boucle avec break au lieu de tester le reste. Dans l’arbre ci-dessus, le nœud 2, 2, 3 avec 1 restant examine 3, constate qu’il ne convient pas et n’examine jamais 6. La recherche ne visite que les préfixes dont la somme est toujours inférieure ou égale à target, ce qui explique pourquoi les grands tests qui font échouer la première approche ne nécessitent ici que quelques milliers d’appels.

L’ordre de sortie découle du même parcours. À chaque niveau, la boucle essaie d’abord les valeurs les plus petites, et chaque combinaison est écrite dans l’ordre croissant. Deux réponses diffèrent pour la première fois au niveau où leurs chemins se séparent ; le chemin qui prend la valeur la plus petite à cet endroit est exploré en premier, et les réponses arrivent donc dans l’ordre lexicographique. Une combinaison ne peut jamais être le préfixe d’une autre, puisque les valeurs sont positives et que les deux atteignent le même total.

Algorithme

Triez les candidats par ordre croissant.
Écrivez backtrack(start, remaining), qui partage une seule liste path. Si remaining vaut 0, enregistrez une copie de path.
Sinon, parcourez i de start jusqu’à la fin. Si nums[i] > remaining, arrêtez la boucle : toutes les valeurs suivantes sont plus grandes.
Ajoutez nums[i], appelez backtrack(i, remaining-nums[i]) avec i, et non i + 1, afin que la valeur puisse être répétée, puis retirez-la.
Appelez backtrack(0, target) et renvoyez les combinaisons enregistrées, déjà dans l’ordre lexicographique.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break  # sorted, so every later value is too big as well
            path.append(nums[i])
            backtrack(i, remaining - nums[i])  # i, not i + 1: nums[i] may repeat
            path.pop()

    backtrack(0, target)
    return result

Pièges et cas limites

La plupart des mauvaises réponses sont dues à l’ordre de la recherche, et non aux calculs.

Parcourir tous les candidats à chaque niveau, au lieu de commencer à l’index courant, crée [2, 3, 3], [3, 2, 3] et [3, 3, 2] comme trois réponses. Trier chaque réponse et supprimer les doublons ensuite donne la bonne liste, mais demande exponentiellement plus de travail.
Récursiver avec i + 1 au lieu de i fait que chaque valeur ne peut apparaître qu’une seule fois ; [2, 2, 2, 2] est donc absent.
Enregistrer path lui-même au lieu d’une copie : toutes les réponses enregistrées sont alors la même liste, que le retour sur trace aura vidée à la fin.
Utiliser break avec des candidats que tu n’as pas triés. Avec [6, 2, 3] et 2 comme reste à atteindre, la boucle s’arrête à 6 et n’essaie jamais 2.
Renvoyer les combinaisons dans l’ordre suggéré par l’entrée non triée. La liste attendue est en ordre lexicographique, que la recherche avec tri produit sans tri supplémentaire.
En Lua et en R, les tableaux commencent à 1 ; le premier appel commence donc à l’index 1 et la boucle va jusqu’à la longueur du tableau.

Questions fréquentes4

Quelle est la complexité temporelle de Combination Sum ?

La recherche avec retour sur trace est exponentielle. Avec n candidats, une cible t et le plus petit candidat m, une combinaison contient au plus t/m valeurs et chaque étape offre au plus n choix, ce qui borne le travail à O(n^(t/m)). L’élagage sur les candidats triés maintient le nombre réel d’appels bien en dessous de cette limite, car la recherche ne visite que les préfixes dont la somme reste inférieure ou égale à t. L’espace supplémentaire est de O(t/m) pour le chemin actuel et la pile d’appels, auquel s’ajoute la sortie.

Pourquoi appelez-vous récursivement avec i et non i + 1 dans Combination Sum ?

La récursion avec i permet de reprendre la même valeur candidate, ce qui permet d’utiliser une valeur plusieurs fois. La récursion avec i + 1 la dépasse, ce qui transforme le problème en une variante où chaque candidate est utilisée au plus une fois. L’autre moitié de la règle est tout aussi importante : ne jamais revenir à un indice antérieur à i maintient chaque combinaison en ordre croissant et évite les doublons.

Comment éviter les combinaisons en double sans utiliser d’ensemble ?

Générez chaque combinaison dans un ordre fixe, croissant. L’indice de départ l’impose : après avoir placé nums[i], la recherche ne considère que nums[i] et les valeurs suivantes. Chaque combinaison a alors exactement un chemin dans l’arbre de recherche ; elle est donc produite une seule fois, sans qu’un ensemble ni une déduplication finale soient nécessaires.

Peut-on résoudre Combination Sum avec la programmation dynamique ?

Oui. Conservez, pour chaque total de 0 à la cible, la liste des combinaisons qui permettent de l’atteindre, et ajoutez un candidat à la fois afin que les valeurs de chaque liste restent dans l’ordre croissant ; c’est la même idée que pour compter les façons de rendre la monnaie. Cette méthode n’explore jamais deux fois une impasse, mais elle stocke chaque combinaison partielle pour chaque total, ce qui demande beaucoup plus de mémoire que le retour sur trace, et la liste finale devra peut-être être triée. Comme la sortie elle-même peut être de taille exponentielle, le retour sur trace est généralement la solution retenue.

Python

def combinationSum(candidates, target):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

candidates = [6, 2, 3]
target = 8

Attendu

[[2, 2, 2, 2], [2, 3, 3], [2, 6]]