Partition en sous-ensembles de somme égale

Étant donné un tableau non vide d’entiers positifs nums, déterminez si vous pouvez le partitionner en deux sous-ensembles de somme égale. Par exemple, [1, 5, 11, 5] peut être partitionné en [1, 5, 5] et [11], dont la somme vaut 11 dans les deux cas. Si la somme totale est impaire, la réponse est immédiatement False. Sinon, nous devons trouver un sous-ensemble dont la somme vaut total_sum // 2 : il s’agit d’un problème classique de somme de sous-ensembles.

La réduction clé : si la somme totale S est paire et qu’un sous-ensemble a pour somme S//2, les éléments restants ont automatiquement aussi pour somme S//2. Ainsi, Partition Equal Subset Sum se ramène à la question suivante : un sous-ensemble de nombres a-t-il pour somme S//2 ? Il s’agit du problème classique, NP-complet, de la somme de sous-ensembles, que nous résolvons avec le DP du sac à dos 0/1 en temps O(n × S).

Définissez un tableau booléen dp[c] dans lequel dp[c] = True signifie qu’il existe un sous-ensemble dont la somme est exactement c. Initialisez dp[0] = True (la somme de l’ensemble vide vaut 0) et tous les autres éléments à False. Pour chaque nombre num, parcourez la capacité de target jusqu’à num en descendant (parcours inverse du sac à dos 0/1), puis définissez dp[c] = dp[c] or dp[c - num].

Pour [1, 5, 11, 5], total=22 et target=11. Au départ, dp[0]=True. Après num=1 : dp[1]=True. Après num=5 : dp[5]=True, dp[6]=True. Après num=11 : dp[11]=True (en utilisant seulement 11). Nous avons déjà trouvé dp[11]=True, mais nous continuons à traiter tous les nombres. Réponse finale : dp[11]=True, la partition est donc possible.

Nous pouvons ajouter une sortie anticipée : si dp[target] devient True à un moment quelconque, renvoyez immédiatement True. Cela peut accélérer considérablement les scénarios les plus favorables. De même, si un élément vaut target, nous pouvons renvoyer immédiatement True. Si un élément dépasse target, il ne peut appartenir à aucun sous-ensemble dont la somme vaut la cible, mais nous devons tout de même vérifier les autres éléments.

Une autre possibilité consiste à conserver un ensemble des sommes atteignables. Commencez par {0}. Pour chaque nombre, ajoutez-le à chacune des sommes de l’ensemble courant : reachable = reachable | {s + num for s in reachable}. Filtrez ensuite l’ensemble pour ne conserver que les sommes qui ne dépassent pas la cible. À la fin, vérifiez si target appartient à l’ensemble. Cette approche est intuitive, mais elle peut utiliser davantage de mémoire et s’avérer plus lente en pratique.

L’approche par DP s’exécute en temps O(n × S), où S = sum(nums), et utilise un espace O(S) pour le tableau booléen. Pour les contraintes de LeetCode (n ≤ 200, somme ≤ 20 000), cela représente au plus 4 000 000 opérations — très rapide. L’approche par ensemble a la même complexité asymptotique, mais peut être plus lente en pratique en raison du surcoût lié à la construction des ensembles.

Voici un problème connexe : compter le nombre de sous-ensembles dont la somme vaut une cible. Remplacez le DP booléen par un DP entier : dp[c] = number of ways to reach sum c. Utilisez l’addition au lieu de OR : dp[c] += dp[c - num]. Initialisez dp[0] = 1. Le parcours inverse reste identique. Cette généralisation montre comment le modèle du sac à dos s’adapte à différentes questions sur les sous-ensembles.

Attendez-vous à des questions de suivi : (1) Et si vous devez renvoyer la partition réelle ? — cela nécessite un DP en 2D pour la reconstruction. (2) Et si les éléments peuvent être négatifs ? — décalez la cible ou utilisez un dictionnaire plutôt qu’un tableau. (3) Quelle est la complexité temporelle ? — O(n × somme). (4) Pouvez-vous améliorer la solution si de nombreux nombres sont identiques ? — oui, utilisez un comptage des fréquences pour réduire le nombre d’itérations externes. Mentionnez toujours ces compromis de manière proactive.

Partition Equal Subset Sum est une application directe du sac à dos 0/1 : les éléments sont les nombres, leurs poids sont égaux à leurs valeurs et la capacité du sac à dos est égale à la cible. Nous cherchons à savoir si la valeur maximale est égale à la cible (problème de faisabilité), et non à déterminer quelle est cette valeur maximale. Le parcours inverse est identique, seule l’opération change : elle passe de max à l’opérateur booléen or. Reconnaître ce lien en entretien témoigne d’une excellente capacité à identifier les modèles.

Voici les cas limites à gérer : (1) tableau de longueur 1 — un seul élément ne peut pas être réparti, donc le résultat est toujours False ; (2) tous les éléments sont identiques et leur nombre est pair — le résultat peut varier selon leurs valeurs ; (3) sommes très élevées — vérifiez les contraintes avant d’allouer le tableau de DP ; (4) éléments supérieurs à la cible — ils peuvent être ignorés, car ils ne peuvent jamais appartenir à un sous-ensemble dont la somme vaut la cible. La vérification de l’élément maximal comme arrêt anticipé traite efficacement le cas (4).

Testez votre compréhension des concepts de structures de données & algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.

Dans cette leçon, vous avez appris : Partition Equal Subset Sum se ramène au problème de la somme de sous-ensembles avec target = total//2, le DP booléen 1D dp[c] utilise un parcours inverse identique à celui du sac à dos 0/1, et cette approche se généralise au comptage des sous-ensembles en remplaçant le OR booléen par une addition entière. Ensuite, nous aborderons la somme cible, en transformant l’attribution de signes en un problème de sac à dos fondé sur la différence des sommes de sous-ensembles.