مجموع مجموعة جزئية متساوية للتقسيم
أعد صياغة مسألة التقسيم باعتبارها حقيبة ظهر 0/1 بهدف يساوي نصف المجموع الكلي، واكتشف إمكانية الحل باستخدام مصفوفة DP منطقية.
مجموع مجموعة جزئية متساوية للتقسيم درس مجاني في DSA Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في DSA Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
نص المسألة
لديكم مصفوفة غير فارغة من الأعداد الصحيحة الموجبة nums، والمطلوب تحديد ما إذا كان يمكن تقسيمها إلى مجموعتين فرعيتين متساويتين في المجموع. على سبيل المثال، يمكن تقسيم [1, 5, 11, 5] إلى [1, 5, 5] و[11]، ومجموع كل منهما 11. إذا كان المجموع الكلي فرديًا، فالإجابة هي False مباشرةً. وإلا، نحتاج إلى إيجاد مجموعة فرعية مجموعها total_sum // 2 — وهي مسألة كلاسيكية من مسائل مجموع المجموعات الفرعية.
الاختزال إلى مسألة مجموع المجموعات الجزئية
الاختزال الأساسي: إذا كان المجموع الكلي S زوجيًا وكانت هناك مجموعة جزئية مجموعها S//2، فستكون قيمة العناصر المتبقية تلقائيًا S//2 أيضًا. لذلك تُختزل مسألة تقسيم المجموع إلى مجموعات جزئية متساوية إلى السؤال التالي: هل توجد مجموعة جزئية من nums مجموعها S//2؟ هذه هي مسألة Subset Sum الكلاسيكية الكاملة ضمن NP، ونحلها باستخدام البرمجة الديناميكية لمسألة حقيبة الظهر 0/1 في زمن O(n × S).
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False # odd sum: impossible
target = total // 2
# Now: does any subset of nums sum to target?مصفوفة DP منطقية
عرّف مصفوفة منطقية dp[c] بحيث تعني dp[c] = True وجود مجموعة جزئية مجموعها يساوي تمامًا c. ابدأ بـ dp[0] = True (فمجموع المجموعة الفارغة يساوي 0) واجعل جميع القيم الأخرى False. لكل عدد num، تكرّر على السعة من target نزولًا إلى num (أي التكرار العكسي في حقيبة الظهر 0/1)، ثم عيّن dp[c] = dp[c] or dp[c - num].
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for c in range(target, num - 1, -1): # backward: 0/1 knapsack
dp[c] = dp[c] or dp[c - num]
return dp[target]
print(canPartition([1, 5, 11, 5])) # True
print(canPartition([1, 2, 3, 5])) # Falseتتبّع المثال خطوة بخطوة
بالنسبة إلى [1, 5, 11, 5]، total=22 وtarget=11. في البداية dp[0]=True. بعد num=1: تصبح dp[1]=True. بعد num=5: تصبح dp[5]=True, dp[6]=True. بعد num=11: تصبح dp[11]=True (باستخدام 11 وحده). لقد وجدنا dp[11]=True بالفعل، لكننا نتابع معالجة جميع الأعداد. الإجابة النهائية: dp[11]=True، ولذلك فإن التقسيم ممكن.
تحسين الإنهاء المبكر
يمكننا إضافة خروج مبكر: إذا أصبحت dp[target] تساوي True في أي نقطة، نعيد True فورًا. وقد يؤدي ذلك إلى تسريع حالات أفضل أداءً بدرجة كبيرة. كذلك، إذا ساوى أي عنصر منفرد target، فيمكننا إعادة True فورًا. أما إذا تجاوز أي عنصر منفرد target، فلا يمكن أن ينتمي إلى أي مجموعة جزئية مجموعها target، لكن لا يزال علينا فحص بقية العناصر.
def canPartition_fast(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
if max(nums) > target: # any element > target makes it impossible
return False
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for c in range(target, num - 1, -1):
dp[c] = dp[c] or dp[c - num]
if dp[target]:
return True # early exit
return dp[target]
print(canPartition_fast([1, 5, 11, 5])) # Trueاستخدام مجموعة Python بدلًا من مصفوفة DP
البديل هو الاحتفاظ بـ مجموعة من المجاميع القابلة للوصول. ابدأ بـ {0}. لكل عدد، أضِفه إلى كل مجموع موجود في المجموعة الحالية: reachable = reachable | {s + num for s in reachable}. رشّح النتائج للاحتفاظ بالمجاميع التي لا تتجاوز target. في النهاية، تحقّق مما إذا كان target موجودًا في المجموعة. هذا الأسلوب بديهي، لكنه قد يستخدم ذاكرة أكبر وقد يكون أبطأ عمليًا.
def canPartition_set(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
reachable = {0}
for num in nums:
reachable = {s + num for s in reachable if s + num <= target} | reachable
return target in reachable
print(canPartition_set([1, 5, 11, 5])) # Trueتحليل التعقيد
يعمل أسلوب DP في زمن O(n × S) حيث S = sum(nums)، ويستخدم مساحة O(S) للمصفوفة المنطقية. وفق القيود في LeetCode (n ≤ 200، sum ≤ 20,000)، لا يتجاوز ذلك 4,000,000 عملية، وهو سريع جدًا. ولأسلوب المجموعة التعقيد التقاربي نفسه، لكنه قد يكون أبطأ عمليًا بسبب تكلفة إنشاء المجموعات.
تعميم: عدّ المجموعات الجزئية ذات مجموع معيّن
هناك مسألة مرتبطة: عدّ عدد المجموعات الجزئية التي مجموعها يساوي target. غيّر DP من نوع منطقي إلى نوع صحيح: dp[c] = number of ways to reach sum c. استخدم الجمع بدلًا من OR: dp[c] += dp[c - num]. ابدأ بـ dp[0] = 1. استخدم التكرار العكسي نفسه. يوضّح هذا التعميم كيف يتكيّف قالب حقيبة الظهر مع أسئلة مختلفة حول المجموعات الجزئية.
def count_subsets(nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for num in nums:
for c in range(target, num - 1, -1):
dp[c] += dp[c - num]
return dp[target]
print(count_subsets([1, 1, 1, 1, 1], 3)) # 10 (C(5,3))أسئلة المتابعة الشائعة في المقابلات
توقّع أسئلة متابعة مثل: (1) ماذا لو احتجت إلى إعادة التقسيم الفعلي؟ — ستحتاج إلى DP ثنائي الأبعاد لإعادة البناء. (2) ماذا لو كان مسموحًا للعناصر بأن تكون سالبة؟ — أزِح target، أو استخدم قاموسًا بدلًا من مصفوفة. (3) ما التعقيد الزمني؟ — O(n × sum). (4) هل يمكنك التحسين إذا كانت أعداد كثيرة متساوية؟ — نعم، استخدم عدّ التكرارات لتقليل عدد التكرارات الخارجية. اذكر هذه المفاضلات استباقيًا دائمًا.
الربط بمسألة حقيبة الظهر 0/1
تُعدّ مسألة تقسيم المجموع إلى مجموعات جزئية متساوية تطبيقًا مباشرًا لمسألة حقيبة الظهر 0/1: العناصر هي الأعداد، والأوزان تساوي القيم، وسعة حقيبة الظهر تساوي target. نحن نسأل عما إذا كانت القيمة القصوى تساوي target (أي عن إمكانية تحقيق الهدف)، وليس عن القيمة القصوى نفسها. التكرار العكسي هو نفسه، ولا يتغير إلا العامل المستخدم من max إلى or المنطقي. إن إدراك هذا الربط في المقابلة يبرهن على قوة التعرّف على الأنماط.
الحالات الحدّية
يجب التعامل مع الحالات الحدّية التالية: (1) مصفوفة طولها 1 — لا يمكن تقسيم العنصر الوحيد، لذا تكون النتيجة دائمًا False؛ (2) جميع العناصر متطابقة وعددها زوجي — قد ينجح التقسيم أو لا ينجح، بحسب قيم العناصر نفسها؛ (3) المجاميع الكبيرة جدًا — تحقّق من القيود قبل تخصيص مصفوفة DP؛ (4) العناصر الأكبر من target — يمكن تخطيها، إذ لا يمكن أن تكون أبدًا جزءًا من مجموعة جزئية مجموعها target. ويتعامل فحص العنصر الأكبر كخروج مبكر مع الحالة (4) بكفاءة.
اختبار سريع
اختبر مدى فهمك لمفاهيم Data Structures & Algorithms — Coding Interview Prep التي تناولها هذا الدرس.
مراجعة الدرس
تعلّمت في هذا الدرس أن: مسألة تقسيم المجموع إلى مجموعات جزئية متساوية تُختزل إلى مسألة مجموع المجموعات الجزئية بحيث يكون target = total//2، وأن مصفوفة DP المنطقية أحادية الأبعاد dp[c] تستخدم التكرار العكسي نفسه المستخدم في حقيبة الظهر 0/1، وأن الأسلوب يتعمم لعدّ المجموعات الجزئية باستبدال OR المنطقي بالجمع الصحيح. بعد ذلك سننتقل إلى مسألة Target Sum، حيث نحوّل تعيين الإشارات إلى مسألة حقيبة ظهر تعتمد على الفرق بين المجاميع الجزئية.
الأسئلة الشائعة
هل درس «مجموع مجموعة جزئية متساوية للتقسيم» مجاني؟
نعم — نص درس «مجموع مجموعة جزئية متساوية للتقسيم» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة DSA Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «مجموع مجموعة جزئية متساوية للتقسيم»؟
أعد صياغة مسألة التقسيم باعتبارها حقيبة ظهر 0/1 بهدف يساوي نصف المجموع الكلي، واكتشف إمكانية الحل باستخدام مصفوفة DP منطقية. تتمرن على DSA Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ DSA Interview Prep؟
لا تُشترط خبرة سابقة. DSA Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «مجموع مجموعة جزئية متساوية للتقسيم»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس DSA Interview Prep هذا؟
نعم. كل درس في DSA Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- حقيبة الظهر 0/1 وتحسين المساحة
- حقيبة الظهر غير المحدودة وتغيير العملات II
- مجموع مجموعة جزئية متساوية للتقسيم
- المجموع المستهدف بإشارات موجبة وسالبة