Partition Equal Subset Sum
Vous disposez d’un tableau nums d’entiers positifs. Déterminez si vous pouvez répartir les valeurs en deux groupes dont les sommes sont égales. Chaque valeur doit appartenir à un seul groupe, et un groupe peut contenir des valeurs provenant de n’importe quelles positions. Renvoyez true si une telle répartition est possible et false sinon.
Fonction
- numsinteger-array
- les valeurs positives à répartir en deux groupes
- Renvoieboolean
- vrai lorsque les valeurs peuvent former deux groupes de sommes égales, faux sinon
Contraintes
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 100
Exemples
- Entrée
- nums = [6, 1, 4, 9, 2]
- Sortie
- true
- Explication
- Le total est de 22, donc chaque groupe doit en avoir 11. Les groupes 9 + 2 et 6 + 1 + 4 font tous deux 11, donc la réponse est
true.
- Entrée
- nums = [4, 7, 2, 9, 6]
- Sortie
- false
- Explication
- Le total est de 28, donc chaque groupe doit en avoir 14. Le groupe qui en contient 9 en a besoin de 5 de plus, et aucune combinaison de 4, 7, 2 et 6 ne donne 5, donc la réponse est
falsemême si le total est pair.
- Entrée
- nums = [1, 2, 3, 5]
- Sortie
- false
- Explication
- Le total est 11. Deux nombres entiers égaux donnent toujours une somme paire, donc un total impair ne peut jamais être partagé et la réponse est
false.
+18 tests cachés à la soumission
Pour aller plus loin
Lorsqu’aucune répartition égale n’est possible, peux-tu renvoyer la plus petite différence possible entre les sommes des deux groupes ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Si les deux groupes ont des sommes égales, que doit valoir chacune de ces sommes en fonction du total de
nums? Et que vous indique immédiatement un total impair ?Il vous suffit de trouver un groupe dont la somme représente la moitié du total ; les valeurs restantes forment l’autre groupe. Réfléchissez à l’ensemble des sommes que peuvent atteindre les premières valeurs, et à la façon dont une valeur supplémentaire modifie cet ensemble.
Conservez un tableau booléen
reach[0..target]avec uniquementreach[0]à true. Pour chaque valeurnum, parcourezsdetargetànumet marquezreach[s]lorsquereach[s-num]est marqué. Parcourir dans l’ordre décroissant empêche d’utiliser chaque valeur deux fois.
Solution
Chaque groupe doit contenir exactement la moitié du total ; la vraie question est donc de savoir si un sous-ensemble de nums donne une somme égale à target = total / 2. Essayer tous les sous-ensembles coûte 2^n, ce qui est irréalisable pour 200 valeurs. Les sommes elles-mêmes sont toutefois petites : target est au plus égal à 200 × 100 / 2 = 10^4. En enregistrant les sommes atteignables, une valeur à la fois, on transforme la recherche en un tableau de sac à dos 0/1 qui se remplit en O(n × sum) étapes.
Essayer chaque sous-ensemble avec la récursion
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Commence par le total. S’il est impair, aucun partage n’est possible, car la somme de deux nombres entiers égaux est toujours paire. Sinon, chaque groupe doit avoir exactement target = total / 2. Une fois que tu as trouvé des valeurs qui donnent target, celles que tu n’as pas choisies constituent à elles seules l’autre moitié. Une seule question suffit donc : existe-t-il un sous-ensemble dont la somme atteint target ?
Parcours les valeurs dans l’ordre et fais un choix pour chacune : la placer dans le premier groupe ou la laisser pour le second. Une fonction auxiliaire reach(i, remaining) indique si les valeurs à partir de l’indice i peuvent totaliser remaining. Elle renvoie true lorsque remaining atteint 0, false lorsqu’il n’y a plus de valeurs ou que la somme passe sous 0 ; sinon, elle essaie les deux possibilités pour nums[i].
Chaque sous-ensemble correspond à un chemin de choix ; la recherche ne peut donc manquer aucun partage, et la réponse est correcte. Elle est lente, car il y a 2^n chemins, et une entrée sans partage oblige à en essayer presque tous. Prenons 199 copies de 100 et un 98 : le total est 19998, la cible 9999 n’est jamais atteinte, et la recherche essaie toutes les façons de choisir au plus 99 des nombres 100, soit environ 4 × 10^59 chemins. Même 40 valeurs donnent 2^40, soit environ 10^12 chemins.
Algorithme
- Additionne les éléments de
nums. Si le total est impair, retournefalse. - Définis
targetcomme la moitié du total. - Écris
reach(i, remaining): retourne true lorsqueremainingvaut 0, et false lorsqueidépasse la dernière valeur ou queremainingest inférieur à 0. - Sinon, retourne
reach(i+1, remaining-nums[i])oureach(i+1, remaining): prends la valeur ou laisse-la. - Retourne
reach(0, target).
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
# Can some of the values from index i on add up to exactly remaining?
def reach(i, remaining):
if remaining == 0:
return True
if i == len(nums) or remaining < 0:
return False
# Put nums[i] in the first group, or leave it for the second one
return reach(i + 1, remaining - nums[i]) or reach(i + 1, remaining)
return reach(0, total // 2)Remplir un tableau par valeur et par somme
Intuition
La récursion pose sans cesse la même question. reach(i, remaining) dépend uniquement de deux nombres : i, de 0 à n, et remaining, de 0 à target. Cela fait au plus (n+1) × (target+1) questions différentes, soit environ 201 × 10001 ≈ 2 × 10^6 aux limites, suffisamment peu pour répondre une seule fois à chacune d’elles.
Construis les réponses en avançant dans un tableau. can[i][s] indique si certaines des i premières valeurs ont une somme égale à s. Sans aucune valeur, seule la somme 0 est possible ; la ligne 0 est donc fausse, sauf pour can[0][0]. La valeur num = nums[i-1] offre deux façons d’obtenir s : ne pas inclure num, auquel cas les valeurs précédentes atteignent déjà s, ou l’inclure, auquel cas les valeurs précédentes atteignent s-num. C’est toute la règle : can[i][s] = can[i-1][s] or can[i-1][s-num], où la seconde partie ne compte que lorsque s ≥ num. Chaque ligne ne lit que la ligne précédente, donc chaque valeur n’est utilisée qu’une seule fois au maximum.
Avec [6, 1, 4, 9, 2] et la cible 11, les sommes atteignables passent de {0} à {0, 6}, puis à {0, 1, 6, 7}, puis à {0, 1, 4, 5, 6, 7, 10, 11}. La somme 11 apparaît après le 4 (6 + 1 + 4), et les lignes suivantes la conservent. La réponse est can[n][target]. Chaque case nécessite un temps constant ; le temps et la mémoire sont donc tous deux en O(n × target).
Algorithme
- Renvoyer
falsesi le total est impair et définirtargetà la moitié de celui-ci. - Créer un tableau de n+1 lignes et de target+1 colonnes, toutes initialisées à false, et définir
can[0][0]à true. - Pour chaque ligne
ide 1 à n, prendrenum = nums[i-1]. - Pour chaque somme
sde 0 àtarget, définircan[i][s]àcan[i-1][s]ou, lorsques ≥ num, àcan[i-1][s-num]. - Renvoyer
can[n][target].
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
target = total // 2
n = len(nums)
# can[i][s] is True when some of the first i values add up to s
can = [[False] * (target + 1) for _ in range(n + 1)]
can[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 and reach s - num with the values before it
can[i][s] = can[i - 1][s] or (s >= num and can[i - 1][s - num])
return can[n][target]Une ligne de sommes, remplie de haut en bas
Intuition
Chaque ligne du tableau ne lit que la ligne au-dessus d’elle ; une seule ligne suffit donc si tu la mets à jour sur place : reach[s] indique si certaines des valeurs vues jusque-là ont pour somme s. Le piège, c’est l’ordre des mises à jour. Si tu parcours s en augmentant, reach[s-num] a peut-être déjà été activé par le même num. Avec [3, 9] et une cible de 6, le 3 marque reach[3], puis le lit pour marquer reach[6], comme si tu avais deux 3, et tu réponds vrai pour une partition qui n’existe pas.
Parcours s en diminuant, de target jusqu’à num. Alors s-num est un indice plus petit que cette valeur n’a pas encore touché, donc reach[s-num] contient toujours la réponse d’avant l’arrivée de num. C’est exactement can[i-1][s-num] du tableau, et cette ligne unique fait le travail de tout le tableau.
Tu peux aussi t’arrêter dès que reach[target] devient vrai, car les valeurs suivantes ne font qu’ajouter des sommes atteignables et n’en suppriment jamais. Dans le pire des cas, il faut toujours O(n × target) étapes, soit environ 2 × 10^6, et la mémoire passe à target + 1 booléens.
Algorithme
- Retourne
falsesi le total est impair et définistargetcomme sa moitié. - Crée
reachavectarget + 1entrées, toutes à false saufreach[0]. - Pour chaque valeur
num, parcourssdetargetjusqu’ànumet définisreach[s]à true lorsquereach[s-num]est true. - Après chaque valeur, retourne
truesireach[target]est true. - Si la boucle se termine, retourne
reach[target], qui vaut false.
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
target = total // 2
# reach[s] is True when some of the values seen so far add up to s
reach = [False] * (target + 1)
reach[0] = True
for num in nums:
# Walk the sums downward so num is used at most once
for s in range(target, num - 1, -1):
if reach[s - num]:
reach[s] = True
if reach[target]:
return True
return reach[target]
Pièges et cas limites
Les mauvaises réponses ici viennent du fait de se fier à une règle gloutonne, de ne pas vérifier si le total est impair et de réutiliser une valeur dans la table à une seule ligne.
- Parcourir les sommes vers le haut dans la version à une seule ligne utilise une valeur plus d’une fois. Avec
[3, 9], la cible est 6 ; le 3 marque d’abord la somme 3, puis la somme 6, et tu réponds vrai. - Ne pas vérifier si le total est impair : pour
[1, 2], le total 3 est arrondi à la baisse, ce qui donne une cible de 1 ; la valeur 1 l’atteint, et tu réponds vrai pour une partition qui ne peut pas exister. - Le remplissage glouton, par exemple en triant et en ajoutant toujours au groupe le plus léger, échoue avec
[3, 3, 2, 2, 2]: il aboutit à 7 contre 5, alors que 3 + 3 = 2 + 2 + 2. - Une valeur supérieure à la cible, comme dans
[2, 2, 2, 10]. Une boucle descendante detargetànums’exécute alors zéro fois, ce qui est correct, mais une plage telle que(num+1):(target+1)en R compte à rebours et casse la table. Ignore ces valeurs. - Un total pair ne suffit pas :
[4, 7, 2, 9, 6]donne une somme de 28 et ne peut toujours pas être partitionné. - En Lua et en R, les tableaux commencent à l’indice 1 ; l’entrée correspondant à la somme
sse trouve donc à l’indices + 1.
Questions fréquentes4
Pourquoi Partition Equal Subset Sum est-il un problème de sac à dos 0/1 ?
Tu as un sac à dos de capacité target = total / 2 et tu dois le remplir exactement, en utilisant chaque valeur au plus une fois. Prendre une valeur ou la laisser de côté constitue le choix 0/1, et la taille d’une valeur est la valeur elle-même. Le tableau des sommes atteignables du sac à dos permet de résoudre ce problème en O(n × target).
Quelle est la complexité temporelle de Partition Equal Subset Sum ?
L’approche par tableau prend un temps de O(n × target), où target correspond à la moitié du total, et nécessite une mémoire de O(target) avec une seule ligne. Avec 200 valeurs d’au plus 100, cela représente environ 2 × 10^6 étapes. La borne augmente avec la taille des valeurs, et pas seulement avec leur nombre ; on parle donc de pseudo-polynomial : avec des valeurs proches de 10^9, aucun tableau ne pourrait tenir, et le problème général est NP-complet.
Pourquoi la boucle interne va-t-elle de la cible vers la valeur ?
Parcourir vers le bas signifie que reach[s-num] est lu avant que cette valeur puisse le modifier ; il décrit donc toujours les valeurs d’avant num. Parcourir vers le haut permettrait d’étendre à nouveau avec num une somme construite avec num, ce qui compte plusieurs fois une même valeur. La boucle ascendante est la bonne pour un nombre illimité de copies, comme dans Coin Change, et la mauvaise ici.
Peut-on résoudre Partition Equal Subset Sum avec un bitset ?
Oui. Stockez les sommes atteignables sous forme de bits d’un grand nombre, en commençant avec uniquement le bit 0 activé. Pour chaque valeur, bits |= bits << num ajoute cette valeur à toutes les sommes atteignables à la fois, et la réponse consiste à vérifier si le bit target est activé. C’est le même tableau, mais chaque mot machine traite 64 sommes à la fois, ce qui est beaucoup plus rapide en pratique.
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.
Python
def canPartition(nums):
# Écrivez le code iciCas 1
Cas 2
Cas 3
Entrée
nums = [6, 1, 4, 9, 2]
Attendu
true