Somme de sous-ensemble et partition
Atteindre une cible avec un sous-ensemble choisi
Somme de sous-ensemble et partition est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
La question de la somme d'un sous-ensemble
Étant donné des nombres et une cible, un sous-ensemble peut-il avoir exactement cette somme ? Il s'agit d'un sac à dos où la valeur est égale au poids.
DP booléen, pas une valeur
Vous suivez ici l'accessibilité, et non un maximum. Soit dp[s] True lorsqu'un sous-ensemble a pour somme exactement s.
dp = [False] * (target + 1)
dp[0] = TrueZéro est toujours accessible
L'ensemble vide a pour somme zéro, donc dp[0] commence à True. Toutes les autres sommes commencent à False, jusqu'à ce qu'un nombre prouve qu'elles sont accessibles.
La transition
Pour chaque nombre, marquez s comme accessible si s - num l'était déjà. Un seul nombre peut faire passer de nombreuses sommes à True.
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]Encore en sens inverse
Chaque nombre n'est utilisé qu'une fois au maximum ; la boucle interne s'exécute donc en sens inverse, comme pour le sac à dos 0/1. Un parcours vers l'avant réutiliserait un nombre.
Lisez le verdict
Après avoir traité tous les nombres, dp[target] répond à la question. True signifie qu'un sous-ensemble valide existe ; False signifie que c'est impossible.
Passez au partitionnement
Le problème du partitionnement demande s'il est possible de diviser le tableau en deux parties de sommes égales. Il se réduit directement au problème de la somme d'un sous-ensemble.
Divisez la somme totale par deux
Si la somme totale est impaire, deux parties égales sont impossibles : répondez immédiatement non. Sinon, la cible est simplement total // 2.
total = sum(nums)
if total % 2:
return False
target = total // 2Réutilisez la somme d'un sous-ensemble
Demandez maintenant simplement si un sous-ensemble atteint total // 2. Si une moitié atteint la cible, le reste forme automatiquement la seconde moitié correspondante.
La complexité
Le coût est de l'ordre de n fois la cible : il s'agit d'une borne pseudo-polynomiale. La méthode est rapide lorsque la cible est petite et lente lorsque les sommes sont énormes.
Une famille de problèmes
La somme de sous-ensembles, le partitionnement et le problème du sac à dos 0/1 reposent sur un même moteur. Repérez la structure prendre ou laisser et réutilisez la même boucle.
Vérification rapide
Vérifiez la réduction du partitionnement.
Récapitulatif
Vous avez résolu la somme de sous-ensembles avec un DP booléen et une boucle inversée, puis réduit le partitionnement à l'atteinte de total // 2. Même moteur, nouveaux résultats. ✅
Questions Fréquemment Posées
La leçon « Somme de sous-ensemble et partition » est-elle gratuite ?
Oui — le texte complet de « Somme de sous-ensemble et partition » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Somme de sous-ensemble et partition » ?
Atteindre une cible avec un sous-ensemble choisi Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Somme de sous-ensemble et partition » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Sac à dos 0/1 : prendre ou laisser
- Sac à dos optimisé en espace
- DP non bornée et rendu de monnaie
- Somme de sous-ensemble et partition