Target Sum

Q: Quel est le lien entre Target Sum et le problème de somme de sous-ensemble ?

Les nombres avec un signe plus doivent avoir pour somme (S + target) / 2 , donc la réponse est le nombre de sous-ensembles de nums ayant cette somme. Toute programmation dynamique qui compte les sous-ensembles de somme donnée résout le problème, à condition d’ajouter deux vérifications : la valeur doit être un nombre entier, et |target| ne doit pas dépasser S .

MoyenProgrammation dynamique Retour sur trace

+10

Vous recevez un tableau nums d’entiers non négatifs et un entier target. Placez un signe plus ou moins devant chaque nombre, conservez leur ordre et évaluez l’expression. Renvoyez le nombre de choix de signes qui rendent l’expression égale à target. Chacun des 2^n choix compte séparément, donc +0 et -0 sont deux choix différents.

Fonction

findTargetSumWays(nums: integer-array, target: integer) → integer

numsinteger-array: les nombres, chacun recevant un signe
targetinteger: la valeur à laquelle l’expression doit être égale
Renvoieinteger: le nombre de choix de signes dont l’expression est égale à la cible

Contraintes

1 ≤ nums.length ≤ 20
0 ≤ nums[i] ≤ 1000
La somme de nums est inférieure ou égale à 1000.
-1000 ≤ target ≤ 1000
La réponse est au plus égale à 2²⁰, bien en dessous de la limite d’un entier signé sur 32 bits.

Exemples

Entrée: nums = [2, 1, 1]target = 2
Sortie: 2
Explication: +2 +1 -1 et +2 -1 +1 valent tous deux 2. Avec un signe moins devant le 2, le maximum que tu peux atteindre est -2 + 1 + 1 = 0, donc aucun autre choix ne fonctionne.

Entrée: nums = [0, 4, 4]target = 0
Sortie: 4
Explication: Les deux 4 doivent avoir des signes opposés, +4 -4 ou -4 +4, et dans les deux cas, le 0 peut avoir l’un ou l’autre signe. Cela donne 2 × 2 = 4 possibilités.

Pour aller plus loin

Peux-tu gérer jusqu’à 40 nombres dont les valeurs peuvent atteindre 10^9, alors qu’aucun tableau indexé par la somme ne tient en mémoire ?

Indices

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

0 sur 3 ouverts

Solution

Chaque nombre a deux signes, donc il y a 2^n expressions. Le comptage par position et total cumulé fusionne les préfixes de signes qui atteignent le même total. Mieux encore, les nombres affectés du signe plus forment un sous-ensemble dont la somme est fixe : le problème revient donc à compter les sous-ensembles ayant une somme donnée, en O(n × S), où S est la somme de nums.

Essaie les deux signes pour chaque nombre

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Parcours les nombres de gauche à droite en tenant un total courant, et fais deux choix à chaque étape : ajoute le nombre ou soustrais-le. Lorsque chaque nombre a un signe, compte 1 si le total est égal à target. Chaque choix de signe correspond à un chemin, donc le nombre de chemins donne la réponse.

Cela fait une feuille par choix : 2^20 ≈ 10^6 feuilles pour 20 nombres, et chaque nombre supplémentaire double le travail.

Algorithme

Écrivez count(i, total), le nombre de façons d’attribuer un signe à nums[i..] lorsque les nombres avant i ont déjà pour somme total.
Si i == n, renvoyez 1 lorsque total == target, sinon 0.
Sinon, renvoyez count(i+1, total + nums[i]) + count(i+1, total - nums[i]).
La réponse est count(0, 0).

def findTargetSumWays(nums, target):
    n = len(nums)

    def count(i, total):
        # Ways to sign nums[i:] so that the whole expression ends at target
        if i == n:
            return 1 if total == target else 0
        return count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])

    return count(0, 0)

Mémoriser en fonction de la position et du total cumulé

Intuition

count(i, total) ne dépend que de i et de total, pas des signes qui ont produit le total. Avec nums = [1, 1, 1, 1], les préfixes +1 -1 et -1 +1 atteignent tous deux le total 0 à la position 2 ; la recherche à partir de là est donc identique. Stocke chaque résultat dès la première fois et réutilise-le.

Le total courant reste entre -S et S ; décale-le de S pour l’utiliser comme indice : memo[i][total + S]. Il y a au plus n × (2S+1) états, soit environ 4 × 10^4 pour 20 nombres dont la somme est 1000, chacun nécessitant un travail constant.

Algorithme

Calculez S = sum(nums) et créez un mémo n × (2S+1) rempli de -1.
Dans count(i, total), renvoyez le cas de base lorsque i == n, comme précédemment.
Si memo[i][total + S] vaut -1, remplissez-le avec count(i+1, total + nums[i]) + count(i+1, total - nums[i]).
Renvoyez la valeur stockée et appelez count(0, 0).

def findTargetSumWays(nums, target):
    n = len(nums)
    whole = sum(nums)
    # memo[i][total + whole]: ways for nums[i:] from this running total, -1 while unknown
    memo = [[-1] * (2 * whole + 1) for _ in range(n)]

    def count(i, total):
        if i == n:
            return 1 if total == target else 0
        if memo[i][total + whole] == -1:
            memo[i][total + whole] = count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
        return memo[i][total + whole]

    return count(0, 0)

Comptez les sous-ensembles dont la somme est égale à (S + target) / 2

Intuition

Soit P la somme des nombres précédés d’un signe plus, et N celle des autres. Alors P - N = target et P + N = S, donc 2P = S + target. Un choix de signes convient exactement lorsque la somme de son groupe de signes plus vaut (S + target) / 2, et chaque sous-ensemble de ce type correspond à un choix de signes.

ways[s] compte les sous-ensembles des nombres vus jusqu’ici dont la somme vaut s, en commençant par ways[0] = 1. Pour chaque nombre x, un sous-ensemble dont la somme vaut s soit n’inclut pas x, soit l’ajoute à un sous-ensemble dont la somme vaut s - x. Parcourez les valeurs de s de la plus grande à la plus petite, afin que ways[s - x] conserve sa valeur d’avant x et qu’aucun nombre ne soit utilisé deux fois. Un 0 ajoute chaque entrée à elle-même, doublant ainsi tous les comptes : les deux signes possibles d’un zéro. Cela représente n × goal additions, au maximum 2 × 10^4.

Algorithme

Calculez S = sum(nums). Si |target| > S ou si S + target est impair, renvoyez 0.
Définissez goal = (S + target) / 2, créez ways avec goal + 1 zéros et définissez ways[0] = 1.
Pour chaque x dans nums, pour s allant de goal à x en ordre décroissant, ajoutez ways[s - x] à ways[s].
Renvoyez ways[goal].

def findTargetSumWays(nums, target):
    whole = sum(nums)
    # plus - minus = target and plus + minus = whole, so plus = (whole + target) / 2
    if abs(target) > whole or (whole + target) % 2 == 1:
        return 0
    goal = (whole + target) // 2
    # ways[s]: how many subsets of the values seen so far add up to s
    ways = [0] * (goal + 1)
    ways[0] = 1
    for x in nums:
        # From the top down, so each value is used at most once
        for s in range(goal, x - 1, -1):
            ways[s] += ways[s - x]
    return ways[goal]

Pièges et cas limites

Ignorer la vérification de parité. Pour [6, 3] et la cible 4, (9 + 4) / 2 est arrondi à 6, et le sous-ensemble {6} donne 1 au lieu de 0.
Ignorer la vérification de plage. Pour [1, 2, 3] et la cible -10, (6 - 10) / 2 = -2, soit une taille de tableau négative.
Remplir ways de bas en haut. Un nombre rejoint alors un sous-ensemble qui l’utilise déjà : [1, 3] avec la cible 2 renvoie 2 au lieu de 1.
Traiter un zéro comme un seul choix. [0, 0, 0, 1, 0, 0] avec la cible -1 a 32 réponses, une pour chaque combinaison de signes des cinq zéros.
Indexer une table de mémoïsation avec un total courant négatif. Décale chaque total de S, ou utilise une table de hachage.

Questions fréquentes3

Quel est le lien entre Target Sum et le problème de somme de sous-ensemble ?

Les nombres avec un signe plus doivent avoir pour somme (S + target) / 2, donc la réponse est le nombre de sous-ensembles de nums ayant cette somme. Toute programmation dynamique qui compte les sous-ensembles de somme donnée résout le problème, à condition d’ajouter deux vérifications : la valeur doit être un nombre entier, et |target| ne doit pas dépasser S.

Quelle est la complexité temporelle de Target Sum ?

La programmation dynamique de comptage des sous-ensembles s’exécute en O(n × S) avec une mémoire de O(S), où S est la somme de nums. La récursion avec mémoïsation a la même complexité temporelle, mais utilise un tableau de n × (2S+1). Essayer chaque signe prend O(2^n).

Peut-on résoudre Target Sum avec une table de hachage des totaux cumulés ?

Oui. Associe chaque total cumulé atteignable au nombre de préfixes de signes qui y mènent, en commençant par {0: 1}, puis construis la carte suivante à partir de total + x et total - x pour chaque nombre. La réponse est le compte associé à target. C’est la récursion mémoïsée exécutée vers l’avant, en le même temps O(n × S).

def findTargetSumWays(nums, target):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

nums = [2, 1, 1]
target = 2

Résultat attendu

Target Sum

Fonction

Contraintes

Exemples

Indices

Solution

Essaie les deux signes pour chaque nombre

Mémoriser en fonction de la position et du total cumulé

Comptez les sous-ensembles dont la somme est égale à (S + target) / 2

Pièges et cas limites

Questions fréquentes3

Problèmes similaires