Combination Sum

Q: Pourquoi fais-tu la récursion avec i et non avec i + 1 dans Combination Sum ?

La récursion avec i permet à la valeur suivante d’être à nouveau le même candidat, ce qui permet d’utiliser une valeur plusieurs fois. La récursion avec i + 1 passe au candidat suivant, de sorte que chaque candidat ne peut être utilisé qu’une seule fois au maximum.

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

Oui. Pour chaque total de 0 à target , conserve les combinaisons qui l’atteignent, en ajoutant un candidat à la fois afin que chaque liste reste triée par ordre croissant. Cette méthode n’explore jamais deux fois une impasse, mais elle stocke chaque combinaison partielle pour chaque total, ce qui coûte beaucoup plus de mémoire. Comme la sortie elle-même peut être exponentielle, le retour sur trace est la solution habituelle.

MoyenRetour sur trace

+10

On te donne une liste candidates de différents entiers positifs et un entier positif target. Trouve toutes les combinaisons de candidats dont la somme est exactement égale à target, en utilisant chaque candidat autant de fois que tu le souhaites. [2, 3, 3] et [3, 2, 3] représentent la même combinaison.

Retourne chaque combinaison dans l’ordre croissant, et les combinaisons dans l’ordre lexicographique : à la première position où deux combinaisons diffèrent, celle qui contient la plus petite valeur 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 et autant de fois que vous le souhaitez
targetinteger: le total que chaque combinaison doit atteindre exactement
Renvoieinteger-2d-array: chaque combinaison dont la somme est égale à la cible, chacune en ordre croissant, listées dans l’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, 2 + 3 + 3 et 2 + 6 font tous 8, classés selon leur deuxième valeur. Sans 2, il ne reste que des 3 et des 6, et leurs sommes 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, et [3, 3, 5] vient en premier parce que sa deuxième valeur, 3, est inférieure à 4. Aucun mélange de 4 et de 5 uniquement ne donne 11.

Pour aller plus loin

Chaque candidat peut désormais être utilisé au plus une fois, et candidates peut contenir des valeurs répétées. Comment modifier la recherche afin 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

Le piège consiste à construire deux fois la même combinaison : 2, 3, 3 et 3, 2, 3 correspondent à une seule réponse. Construisez chaque combinaison dans l’ordre croissant afin qu’elle n’ait qu’un seul chemin, et triez les candidats pour qu’une branche s’arrête dès que la valeur suivante est supérieure à ce qu’il reste.

Essayez chaque décompte de chaque candidat

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Une combinaison est entièrement décrite par le nombre d’exemplaires de chaque candidat qu’elle utilise : [2, 3, 3] correspond à un 2, deux 3 et aucun 6. Essaie chaque quantité pour chaque candidat trié, de target / c jusqu’à 0, en conservant les choix dont le total est exactement target. Chaque combinaison correspond à une seule liste de quantités, donc aucune n’est trouvée deux fois. En commençant par les quantités les plus élevées, on obtient un ordre lexicographique : là où deux réponses diffèrent pour la première fois, celle qui contient davantage d’exemplaires d’une valeur conserve cette valeur, tandis que l’autre contient une valeur plus grande.

Pour [2, 3, 6] et une cible de 8, il y a 5 × 3 × 2 = 30 feuilles pour 3 réponses. Chaque candidat supérieur à target / 2 double le nombre de feuilles ; ainsi, 40 candidats de ce type donnent 2^40, soit environ 10^12.

Algorithme

Trie les candidats et conserve un compte pour chaque valeur.
Dans choose(i, total), essaie chaque compte k de target / nums[i] à 0, puis appelle choose(i + 1, total + k × nums[i]).
Une fois qu’une valeur a été attribuée à chaque compte, conserve la combinaison si total est égal à target et écris-la à partir des comptes.
Appelle choose(0, 0).

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

Après avoir placé nums[i], la valeur suivante peut être à nouveau nums[i] ou n’importe quelle valeur ultérieure, jamais une valeur précédente. Une combinaison a un seul ordre croissant, donc elle n’a qu’un seul chemin, et [3, 2, 3] n’est jamais construite.

Pour [2, 3, 6] trié et la cible 8, les chemins 2, 2, 2, 2 et 2, 3, 3 et 2, 6 atteignent 8. Le chemin 2, 2, 3 laisse 1 et s’arrête sans examiner 6, et 3, 3 laisse 2, qui ne correspond à aucune valeur. Cela représente 12 appels contre les 30 feuilles du comptage.

À chaque niveau, la boucle essaie d’abord les valeurs les plus petites, donc les réponses arrivent dans l’ordre lexicographique. Aucune réponse n’est le préfixe d’une autre, puisque les valeurs sont positives et que les deux atteignent le même total.

Algorithme

Triez les candidats.
Dans backtrack(start, remaining), enregistrez une copie du path partagé lorsque remaining vaut 0.
Sinon, parcourez i à partir de start. Si nums[i] > remaining, interrompez la boucle : toutes les valeurs suivantes sont plus grandes.
Ajoutez nums[i], appelez backtrack(i, remaining - nums[i]), puis retirez-le.
Appelez backtrack(0, target) et renvoyez les combinaisons enregistrées.

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

Parcourir tous les candidats à chaque niveau, au lieu de commencer à l’indice actuel. [2, 3, 3], [3, 2, 3] et [3, 3, 2] donnent alors trois réponses.
Rappeler la fonction avec i + 1 au lieu de i. Chaque valeur peut alors apparaître une seule fois, donc [2, 2, 2, 2] est omis.
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 arrière a vidée à la fin.
Utiliser break sur des candidats que tu n’as pas triés. Avec [6, 2, 3] et 2 restants, la boucle s’arrête à 6 et n’essaie jamais le 2.

Questions fréquentes3

Quelle est la complexité temporelle de Combination Sum ?

La recherche avec retour arrière a une complexité exponentielle. Avec n candidats, une cible t et le plus petit candidat m, une combinaison contient au maximum t/m valeurs, avec au plus n choix chacune : O(n^(t/m)). L’espace supplémentaire est de O(t/m) pour le chemin et la pile d’appels, auquel s’ajoute la sortie.

Pourquoi fais-tu la récursion avec i et non avec i + 1 dans Combination Sum ?

La récursion avec i permet à la valeur suivante d’être à nouveau le même candidat, ce qui permet d’utiliser une valeur plusieurs fois. La récursion avec i + 1 passe au candidat suivant, de sorte que chaque candidat ne peut être utilisé qu’une seule fois au maximum.

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

Oui. Pour chaque total de 0 à target, conserve les combinaisons qui l’atteignent, en ajoutant un candidat à la fois afin que chaque liste reste triée par ordre croissant. Cette méthode n’explore jamais deux fois une impasse, mais elle stocke chaque combinaison partielle pour chaque total, ce qui coûte beaucoup plus de mémoire. Comme la sortie elle-même peut être exponentielle, le retour sur trace est la solution habituelle.

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

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

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