المجموع المستهدف بإشارات موجبة وسالبة
حوّل مسألة إسناد المجموع المستهدف إلى مسألة حقيبة ظهر تعتمد على فرق مجموع المجموعات الجزئية، وحلّها في زمن O(n × sum).
المجموع المستهدف بإشارات موجبة وسالبة درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
مسألة مجموع الهدف
لديك مصفوفة أعداد صحيحة nums وعدد صحيح target، وعيّن إشارة + أو - لكل عدد بحيث تساوي قيمة التعبير الناتج target. أعد عدد الطرق المختلفة لتحقيق ذلك. على سبيل المثال، عند nums=[1,1,1,1,1] وtarget=3، توجد 5 طرق (اختيار 4 عناصر موجبة وعنصر واحد سالب، مع اختلاف الموضع).
القوة الغاشمة: تعداد DFS
يعيّن أسلوب DFS لكل عدد إشارة + أو - ثم يستدعي نفسه تكراريًا، ويعيد عدد العقد الورقية التي تصل إلى target. هذا الأسلوب صحيح، لكنه يمتلك تعقيدًا زمنيًا O(2^n)، أي إنه أُسّي. فعندما تكون n=20، يتطلب أكثر من مليون استدعاء تكراري. يجدر بك ذكر أسلوب DFS أولًا، ثم الانتقال سريعًا إلى تحسين DP.
def findTargetSumWays_dfs(nums, target):
count = [0]
def dfs(i, current_sum):
if i == len(nums):
if current_sum == target:
count[0] += 1
return
dfs(i+1, current_sum + nums[i])
dfs(i+1, current_sum - nums[i])
dfs(0, 0)
return count[0]
print(findTargetSumWays_dfs([1,1,1,1,1], 3)) # 5DFS مع التخزين المؤقت
أضف التخزين المؤقت إلى DFS؛ فالحالة هي (index, current_sum). وبما أن current_sum يمكن أن يتراوح من -total إلى +total، فهناك O(n × total) من الحالات الفريدة. مع التخزين المؤقت، يعمل DFS في زمن ومساحة O(n × total). هذا الحل صالح ومقبول في المقابلات، لكن DP القائم على التحويل أكثر أناقة وكفاءة من حيث المساحة.
from functools import lru_cache
def findTargetSumWays_memo(nums, target):
total = sum(nums)
@lru_cache(maxsize=None)
def dp(i, remaining):
if i == len(nums):
return 1 if remaining == 0 else 0
return dp(i+1, remaining - nums[i]) + dp(i+1, remaining + nums[i])
return dp(0, target)
print(findTargetSumWays_memo([1,1,1,1,1], 3)) # 5التحويل الرياضي
لتكن P مجموعة الأعداد التي أُسندت إليها الإشارة +، ولتكن N مجموعة الأعداد التي أُسندت إليها الإشارة -. عندئذٍ: sum(P) - sum(N) = target وsum(P) + sum(N) = total. بالجمع نحصل على: 2 × sum(P) = target + total، ومنه sum(P) = (target + total) / 2. تختزل المسألة إلى: عدّ المجموعات الجزئية من nums التي مجموعها (target + total) / 2. وهذه هي بالضبط صيغة عدّ المجموعات الجزئية من مسألة حقيبة الظهر 0/1.
# sum(P) - sum(N) = target
# sum(P) + sum(N) = total
# => 2*sum(P) = target + total
# => sum(P) = (target + total) / 2
# Count subsets with sum = new_target = (target + total) // 2
print('Reduction: count subsets summing to (target + total) // 2')فحوصات الصلاحية قبل DP
قبل تشغيل DP، تحقّق مما يلي: (1) يجب أن يكون target + total زوجيًا، وإلا فلن يكون sum(P) عددًا صحيحًا، وتصبح المسألة مستحيلة؛ (2) إذا كان abs(target) > total، فهذا يعني أن الوصول إلى target مستحيل حتى لو اتفقت جميع الإشارات. إذا فشل أي من الفحصين، فأعد 0 فورًا. تتعامل هذه الفحوصات مع الحالات الحدّية بوضوح دون إضافة حالات خاصة داخل حلقة DP.
def findTargetSumWays(nums, target):
total = sum(nums)
if (target + total) % 2 != 0:
return 0 # sum(P) would be non-integer
if abs(target) > total:
return 0 # impossible to reach
new_target = (target + total) // 2
# Count subsets summing to new_target
dp = [0] * (new_target + 1)
dp[0] = 1
for num in nums:
for c in range(new_target, num - 1, -1):
dp[c] += dp[c - num]
return dp[new_target]
print(findTargetSumWays([1,1,1,1,1], 3)) # 5تتبّع مثال صغير
بالنسبة إلى nums=[1,1,1,1,1] وtarget=3: total=5 وnew_target=(3+5)//2=4. نعدّ المجموعات الجزئية التي مجموعها 4 من [1,1,1,1,1]. وهذا يساوي C(5,4)=5 (اختيار أربعة من الواحدات لتكون موجبة، والخامسة سالبة: 1+1+1+1-1=3). يعيد DP القيمة 5 بشكل صحيح. يحوّل هذا التحويل بأناقة مسألة تعيين الإشارات إلى مسألة قياسية لعدّ المجموعات الجزئية.
التعامل مع الأصفار في nums
إذا احتوت nums على أصفار، فإن إسناد + أو - إلى الصفر لا يغيّر المجموع. لذلك يضاعف كل صفر عدد التعيينات الصحيحة. يتعامل DP مع ذلك تلقائيًا: عند معالجة num=0، تعمل الحلقة الداخلية range(new_target, -1, -1) من new_target نزولًا إلى 0، وتصبح dp[c] += dp[c - 0] = dp[c]، فتتضاعف جميع المجاميع القابلة للوصول. لا حاجة إلى معالجة خاصة إذا استخدمت range(new_target, num-1, -1)، التي تبدأ من new_target وتنخفض إلى 0 عندما يكون num=0.
# With zeros: each zero doubles the count
print(findTargetSumWays([0, 0, 1], 1)) # 4
# Assignments: +0+0+1, +0-0+1, -0+0+1, -0-0+1 = all give sum 1مقارنة التعقيد
يعمل DFS بالقوة الغاشمة في زمن O(2^n). ويعمل DFS مع التخزين المؤقت في زمن O(n × total) ومساحة O(n × total). أما DP أحادي الأبعاد القائم على التحويل فيعمل في زمن O(n × new_target) ومساحة O(new_target)، حيث new_target ≤ total. ويستخدم DP أحادي الأبعاد مساحة أقل بكثير من التخزين المؤقت، لأنه يتخلص من بُعد الفهرس عبر التحويل.
الصلة بمسائل حقيبة الظهر الأخرى
تربط مسألة Target Sum بين عدة مفاهيم في حقيبة الظهر: فهي تبدأ كمسألة تعيين، ثم تتحول إلى مسألة مجموع المجموعات الجزئية (مثل مسألة تقسيم المجموع إلى مجموعات جزئية متساوية)، وتستخدم قالب التكرار العكسي نفسه لحقيبة الظهر 0/1، لكن مع العدّ (مثل مسألة Coin Change II). يتيح لك إتقان هذه الروابط تصنيف المسائل الجديدة بسرعة في المقابلات، وذلك بالاعتماد على تشابهها البنيوي مع الأنماط المعروفة.
الحالات الحدّية وملاحظات المقابلة
الحالات المهمة: (1) target = total: توجد طريقة واحدة فقط (جميع الإشارات موجبة)؛ (2) target = -total: توجد طريقة واحدة فقط (جميع الإشارات سالبة)؛ (3) target = 0 مع كون جميع العناصر أصفارًا: الإجابة هي 2^n؛ (4) total كبير جدًا مع n صغير — يكون حجم مصفوفة DP أحادية الأبعاد محدودًا بـ total/2. في المقابلات، اشرح التحويل شفهيًا قبل كتابة الشيفرة، فهو الفكرة غير البديهية التي تميّز المرشحين الأقوياء.
بديل DP ثنائي الأبعاد دون تحويل
من دون التحويل، عرّف dp[i][s] بأنه عدد طرق إسناد الإشارات إلى أول i أعداد للوصول إلى المجموع s. يمكن أن يكون المجموع سالبًا، لذا أزِحه بمقدار total، واستخدم dp[i][s + total]. يتطلب ذلك جدولًا ثنائي الأبعاد حجمه (n+1) × (2*total+1). ورغم صحة هذا الأسلوب، فإنه يستخدم مساحة أكبر ويصعب ترميزه بسرعة تحت ضغط المقابلة مقارنةً بحقيبة الظهر أحادية الأبعاد بعد التحويل.
اختبار سريع
اختبر مدى فهمك لمفاهيم Data Structures & Algorithms — Coding Interview Prep التي تناولها هذا الدرس.
مراجعة الدرس
تعلّمت في هذا الدرس أن: مسألة Target Sum تحوّل تعيين الإشارات إلى عدّ المجموعات الجزئية التي مجموعها (target + total) / 2، وأن حقيبة الظهر 0/1 أحادية الأبعاد مع التكرار العكسي تعدّ المجموعات الجزئية في زمن O(n × new_target) ومساحة O(new_target)، وأن فحوصات الصلاحية المبكرة (المجموع الفردي، |target| > total) تمنع تشغيل DP دون حاجة. بعد ذلك سننتقل إلى عالم أقصر المسارات مع خوارزمية Dijkstra وطابور الأولوية.
الأسئلة الشائعة
هل درس «المجموع المستهدف بإشارات موجبة وسالبة» مجاني؟
نعم — نص درس «المجموع المستهدف بإشارات موجبة وسالبة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «المجموع المستهدف بإشارات موجبة وسالبة»؟
حوّل مسألة إسناد المجموع المستهدف إلى مسألة حقيبة ظهر تعتمد على فرق مجموع المجموعات الجزئية، وحلّها في زمن O(n × sum). تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «المجموع المستهدف بإشارات موجبة وسالبة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- حقيبة الظهر 0/1 وتحسين المساحة
- حقيبة الظهر غير المحدودة وتغيير العملات II
- مجموع مجموعة جزئية متساوية للتقسيم
- المجموع المستهدف بإشارات موجبة وسالبة