Subset Sum Problem
nums contient des entiers positifs, et target est un entier positif. Peux-tu choisir certaines des valeurs, chaque position au plus une fois, de façon à ce que leur somme soit exactement égale à target ? Renvoie true si c’est possible et false si aucun choix ne convient.
Fonction
- numsinteger-array
- les valeurs positives parmi lesquelles vous pouvez choisir
- targetinteger
- la somme exacte que les valeurs choisies doivent atteindre
- Renvoieboolean
- vrai lorsque certaines des valeurs totalisent exactement target, faux sinon
Contraintes
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 1041 ≤ target ≤ 104
Exemples
- Entrée
- nums = [8, 3, 11, 5, 7]target = 15
- Sortie
- true
- Explication
- 8 + 7 = 15, donc la réponse est
true. Le choix 3 + 5 + 7 fonctionne aussi ; un seul choix suffit.
- Entrée
- nums = [6, 9, 12, 15]target = 20
- Sortie
- false
- Explication
- Chaque valeur est un multiple de 3, donc chaque somme de ces valeurs est également un multiple de 3. 20 ne l’est pas, donc la réponse est
false.
- Entrée
- nums = [4, 1, 2]target = 8
- Sortie
- false
- Explication
- Les trois valeurs réunies font 4 + 1 + 2 = 7, ce qui est inférieur à 8 ; aucun choix ne peut donc atteindre ce résultat et la réponse est
false.
Pour aller plus loin
Deux valeurs égales à des positions différentes comptent comme des choix différents. Combien de choix atteignent target ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Commence avec
nums[0]. Si ta sélection l’inclut, les autres valeurs doivent donnertarget-nums[0]. Sinon, elles doivent donnertarget. C’est la même question sur un tableau plus court.La possibilité de former une somme
ravec les valeurs à partir de la positionidépend uniquement deiet der, etrne dépasse jamaistarget. Il y a donc au maximum environ 200 × 10^4 questions différentes, et chacune peut être résolue une seule fois.Utilisez un booléen par somme, de 0 à
target, avec seulement la somme 0 atteignable au départ. Ajoutez les valeurs une par une : une sommesdevient atteignable lorsques-numl’était déjà. Mettez à jour les sommes de la plus grande à la plus petite afin qu’une valeur ne soit pas utilisée deux fois, puis lisez la réponse àtarget.
Solution
Un choix correspond à un oui ou à un non pour chaque valeur, donc 200 valeurs donnent 2^200 choix. Cependant, seuls les totaux jusqu’à target ≤ 10^4 comptent. Note les totaux que les valeurs traitées jusqu’ici peuvent former : chaque nouvelle valeur décale cet enregistrement de sa taille, et la recherche devient un tableau de booléens de dimensions n × target.
Prendre ou ignorer chaque valeur
Correcte, mais ne termine pas sur les plus gros tests
Intuition
canMake(i, remaining) demande si les valeurs à partir de la position i peuvent donner exactement remaining. Prends nums[i] si elle convient, ce qui laisse remaining-nums[i] pour la suite ; si cela échoue, ignore-la. Chaque sélection constitue un chemin, donc la recherche trouve une sélection dès qu’il en existe une.
Lorsqu’il n’en existe aucune, elle les parcourt toutes. Avec 200 multiples de 3, chacun valant au plus 300, et une cible de 9998, aucune sélection ne fonctionne, et pourtant n’importe quelles 33 valeurs restent en dessous de la cible : plus de 10^37 chemins.
Algorithme
- Écris
canMake(i, remaining). - Un
remainingde 0 signifie que la sélection est terminée : retourne true. S’il ne reste plus de valeurs et qu’il reste encore quelque chose à obtenir, retourne false. - Si
nums[i] ≤ remaininget quecanMake(i+1, remaining-nums[i])est true, retourne true. - Sinon, retourne
canMake(i+1, remaining). - Retourne
canMake(0, target).
def isSubsetSum(nums, target):
n = len(nums)
# Can some of nums[i], nums[i+1], ... add up to exactly remaining?
def can_make(i, remaining):
if remaining == 0:
return True
if i == n:
return False
if nums[i] <= remaining and can_make(i + 1, remaining - nums[i]):
return True # take nums[i]
return can_make(i + 1, remaining) # skip it
return can_make(0, target)Remplir un tableau des sommes atteignables
Intuition
La récursion dépend uniquement d’une position et d’une somme restante comprise entre 0 et target, et de nombreux chemins atteignent la même paire. Remplissez plutôt un tableau. made[i][s] vaut true lorsqu’une sélection parmi les i premières valeurs donne exactement la somme s ; la sélection vide donne 0. Avec num = nums[i-1], la somme s est obtenue si elle l’était sans num, made[i-1][s], ou si num complète s-num, made[i-1][s-num] avec s ≥ num.
Dans le premier exemple, après le 8, les sommes obtenues sont 0 et 8. Le 3 ajoute 3 et 11, le 11 ajoute uniquement 14, le 5 ajoute 5 et 13, et 8 + 7 atteint 15. Aux limites, le tableau compte 201 × 10001 cellules, soit environ 2 × 10^6 étapes.
Algorithme
- Alloue
madeavec n+1 lignes et target+1 booléens, tous à false. Marquemade[0][0]comme true pour le choix vide. - La ligne
itraite la valeurnum = nums[i-1], pouri= 1 à n. - Pour chaque somme
sde 0 àtarget, définismade[i][s]àmade[i-1][s]. - Si
s ≥ numet quemade[i-1][s-num]est true, définismade[i][s]à true. - Renvoie
made[n][target].
def isSubsetSum(nums, target):
n = len(nums)
# made[i][s]: some of the first i values add up to exactly s
made = [[False] * (target + 1) for _ in range(n + 1)]
made[0][0] = True
for i in range(1, n + 1):
num = nums[i - 1]
for s in range(target + 1):
# leave num out, or put it in on top of a sum of s-num
made[i][s] = made[i - 1][s] or (s >= num and made[i - 1][s - num])
return made[n][target]Une ligne de sommes, mise à jour depuis le haut
Intuition
Chaque ligne ne lit que la ligne qui la précède, donc un seul tableau made[s] peut la contenir. Parcourez-le en montant et une valeur se réutilise elle-même : avec nums = [5] et une cible de 10, s = 5 devient vrai, puis s = 10 lit cette nouvelle entrée et utilise le 5 deux fois.
Parcourez plutôt target jusqu’à num en descendant. La lecture à s-num accède à une cellule inférieure que le parcours n’a pas réécrite, donc elle voit la ligne d’avant num. Une somme atteignable le reste, donc vous pouvez vous arrêter dès que made[target] est vrai. La mémoire passe à target + 1 booléens.
Algorithme
- Commence avec un tableau unique de booléens de taille
target + 1, dans lequel seulmade[0]vaut true. - Prends les valeurs dans l’ordre. Pour chaque
num, fais décroîtresdetargetànum. - Partout où
made[s-num]est vrai, marquemade[s]. - Arrête-toi avec
truedès quemade[target]est marqué. - Si toutes les valeurs sont utilisées avant cela, la réponse est
false.
def isSubsetSum(nums, target):
# made[s]: some of the values seen so far add up to exactly s
made = [False] * (target + 1)
made[0] = True
for num in nums:
# Downward, so made[s - num] still ignores num
for s in range(target, num - 1, -1):
if made[s - num]:
made[s] = True
if made[target]:
return True
return False
Pièges et cas limites
- Une boucle ascendante sur les sommes utilise une valeur deux fois :
[3]avec une cible de 9 donne vrai. - Oublier
made[0] = true. Chaque somme s’appuie sur la sélection vide, donc toutes les réponses sont fausses. - Choisir les valeurs les plus grandes en premier. Avec
[6, 5, 5]et une cible de 10, prendre 6 laisse 4, que rien ne permet d’obtenir, alors que 5 + 5 = 10. - Une valeur supérieure à
target, comme dans[10000]avec une cible de 1, ne doit rien changer. En Swift,num...targetarrête le programme et, en R,(num+1):(target+1)compte à rebours ; vérifiez donc d’abordnum ≤ target. - En Lua et en R, l’entrée correspondant à la somme
sse trouve à l’indexs + 1.
Questions fréquentes4
Quelle est la complexité temporelle du problème de somme des sous-ensembles ?
La table nécessite un temps de O(n × target), soit environ 2 × 10^6 étapes pour 200 valeurs et une cible de 10^4, et une seule ligne réduit la mémoire à O(target). Le coût dépend de la taille numérique de la cible : la méthode est donc pseudo-polynomiale et inutilisable pour une cible comme 10^18. En général, le problème de la somme de sous-ensemble est NP-complet.
Quel est le lien entre le problème de la somme de sous-ensemble, Partition Equal Subset Sum et le problème du sac à dos 0/1 ?
Le problème de partition en sous-ensembles de somme égale est un problème de somme de sous-ensemble avec target = total / 2, après avoir vérifié que le total est pair. La somme de sous-ensemble est un problème de sac à dos 0/1 où chaque valeur est son propre poids et où le sac doit être rempli exactement ; le tableau contient donc des valeurs booléennes plutôt que les meilleures valeurs.
Le problème de la somme de sous-ensembles fonctionne-t-il avec des nombres négatifs ?
L’idée fonctionne, mais pas le code ci-dessus. Avec des nombres négatifs, les sommes atteignables vont de la somme des nombres négatifs à la somme des nombres positifs ; il faut donc décaler chaque indice de cette somme minimale et remplir la ligne de la même manière. Une valeur supérieure à la somme restante ne peut plus être ignorée.
Comment trouver les valeurs qui donnent le résultat cible ?
Conservez le tableau complet et commencez à made[n][target]. Remontez d’une ligne à la fois : si made[i-1][s] est vrai, nums[i-1] n’était pas nécessaire ; sinon, notez-le et soustrayez-le de s. Vous vous arrêtez lorsque la somme atteint 0, avec une sélection valide.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def isSubsetSum(nums, target):
# Écrivez le code iciTest #1
Test #2
Test #3
Arguments
nums = [8, 3, 11, 5, 7] target = 15
Résultat attendu
true