Somme cible avec signes positifs et négatifs

Étant donné un tableau d’entiers nums et un entier target, attribuez un signe + ou - à chaque nombre afin que l’expression obtenue s’évalue à target. Renvoyez le nombre de façons distinctes de procéder. Par exemple, avec nums=[1,1,1,1,1] et target=3, il existe 5 façons de faire (choisir 4 éléments positifs et 1 élément négatif, à des positions différentes).

Une approche DFS attribue à chaque nombre le signe + ou - et effectue des appels récursifs, en renvoyant le nombre de nœuds feuilles qui atteignent target. Elle est correcte, mais sa complexité temporelle est O(2^n) — elle est donc exponentielle. Pour n=20, cela représente plus d’un million d’appels récursifs. Il est utile de commencer par mentionner l’approche DFS, puis de passer rapidement à l’optimisation par DP.

Ajoutez une mémoïsation à la DFS : l’état est (index, current_sum). Comme current_sum peut varier de -total à +total, il existe O(n × total) états distincts. Avec la mémoïsation, la DFS s’exécute en temps et en espace O(n × total). Cette approche fonctionne et reste valable en entretien, mais le DP fondé sur la transformation est plus élégant et plus économe en espace.

Soit P l’ensemble des nombres auxquels le signe + est attribué, et N l’ensemble de ceux auxquels le signe - est attribué. Alors : sum(P) - sum(N) = target et sum(P) + sum(N) = total. En additionnant, on obtient : 2 × sum(P) = target + total, donc sum(P) = (target + total) / 2. Le problème se réduit à : compter les sous-ensembles de nombres dont la somme vaut (target + total) / 2. Il s’agit exactement de la variante « compter les sous-ensembles » du sac à dos 0/1.

Avant d’exécuter le DP, vérifiez les points suivants : (1) target + total doit être pair (sinon sum(P) n’est pas un entier, ce qui est impossible) ; (2) abs(target) > total signifie que la cible est impossible à atteindre, même si tous les signes sont orientés dans le même sens. Si l’une de ces vérifications échoue, renvoyez immédiatement 0. Ces vérifications traitent proprement les cas limites sans nécessiter de cas particuliers dans la boucle du DP.

Pour nums=[1,1,1,1,1], target=3 : total=5, new_target=(3+5)//2=4. Nous comptons les sous-ensembles dont la somme vaut 4 parmi [1,1,1,1,1]. Il s’agit de C(5,4)=5 (choisir 4 uns comme positifs et le cinquième comme négatif : 1+1+1+1-1=3). Le DP renvoie correctement 5. La transformation associe élégamment le problème d’attribution de signes à un problème standard de comptage de sous-ensembles.

Si nums contient des zéros, attribuer le signe + ou - à un zéro ne modifie pas la somme. Chaque zéro double le nombre d’affectations valides. Le DP gère cela naturellement : lors du traitement de num=0, la boucle interne range(new_target, -1, -1) s’exécute de new_target jusqu’à 0, et dp[c] += dp[c - 0] = dp[c] double toutes les sommes atteignables. Aucun traitement particulier n’est nécessaire si vous utilisez range(new_target, num-1, -1), qui commence à new_target et descend jusqu’à 0 lorsque num=0.

La DFS par force brute est en O(2^n). La DFS avec mémoïsation utilise un temps et un espace O(n × total). Le DP 1D fondé sur la transformation s’exécute en temps O(n × new_target) et utilise un espace O(new_target), où new_target ≤ total. Le DP 1D utilise beaucoup moins d’espace que la mémoïsation, car la transformation élimine la dimension correspondant à l’indice.

La somme cible relie plusieurs concepts du sac à dos : elle commence comme un problème d’attribution, se transforme en somme de sous-ensembles (comme Partition Equal Subset Sum) et utilise le même modèle de parcours inverse du sac à dos 0/1, mais avec du comptage (comme dans Changement de monnaie II). Maîtriser ces liens permet de classer rapidement les nouveaux problèmes d’entretien en fonction de leur ressemblance structurelle avec des modèles connus.

Cas importants : (1) target = total : une seule façon (tous les signes sont positifs) ; (2) target = -total : une seule façon (tous les signes sont négatifs) ; (3) target = 0 avec uniquement des zéros : la réponse est 2^n ; (4) total très élevé mais n petit — la taille du tableau de DP 1D est limitée par total/2. En entretien, expliquez oralement la transformation avant de coder : c’est l’idée non évidente qui distingue les meilleurs candidats.

Sans la transformation, définissez dp[i][s] comme le nombre de façons d’attribuer des signes aux i premiers nombres pour atteindre la somme s. La somme pouvant être négative, décalez-la de total : utilisez dp[i][s + total]. Cela nécessite un tableau 2D de taille (n+1) × (2*total+1). Bien que correcte, cette solution utilise davantage d’espace et est plus difficile à coder rapidement sous la pression d’un entretien que le sac à dos 1D obtenu après transformation.

Dans cette leçon, vous avez appris : la somme cible transforme l’attribution de signes en un comptage de sous-ensembles dont la somme vaut (target + total) / 2, le parcours inverse du sac à dos 0/1 1D compte les sous-ensembles en temps O(n × new_target) et en espace O(new_target), et les vérifications de validité anticipées (somme impaire, |target| > total) évitent une exécution inutile du DP. Ensuite, nous entrerons dans le domaine des plus courts chemins avec l’algorithme de Dijkstra et une file de priorité.