Subset Sum Problem
تحتوي nums على أعداد صحيحة موجبة، وtarget عدد صحيح موجب. هل يمكنك اختيار بعض القيم، بحيث تختار كل موضع مرة واحدة على الأكثر، لكي يكون مجموعها مساويًا تمامًا لـ target؟ أعد true إذا أمكنك ذلك، وfalse إذا لم ينجح أي اختيار.
الدالة
- numsinteger-array
- القيم الموجبة التي يمكنك الاختيار منها
- targetinteger
- المجموع الدقيق الذي يجب أن تصل إليه القيم المختارة
- تُرجعboolean
- صحيحًا عندما يكون مجموع بعض القيم مساويًا تمامًا للهدف، وخاطئًا خلاف ذلك
القيود
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 1041 ≤ target ≤ 104
أمثلة
- المدخلات
- nums = [8, 3, 11, 5, 7]target = 15
- المخرجات
- true
- الشرح
- 8 + 7 = 15، لذا فالإجابة هي
true. وينجح أيضًا اختيار 3 + 5 + 7؛ اختيار واحد يكفي.
- المدخلات
- nums = [6, 9, 12, 15]target = 20
- المخرجات
- false
- الشرح
- كل قيمة هي من مضاعفات 3، لذا فإن كل مجموع لها هو أيضًا من مضاعفات 3. والعدد 20 ليس كذلك، لذا فالإجابة هي
false.
- المدخلات
- nums = [4, 1, 2]target = 8
- المخرجات
- false
- الشرح
- القيم الثلاث معًا تساوي 4 + 1 + 2 = 7، وهو أقل من 8، لذلك لا يمكن لأي اختيار الوصول إليها، والإجابة هي
false.
سؤال إضافي
تُعَدّ قيمتان متساويتان في موضعين مختلفين اختيارين مختلفين. كم اختيارًا يصل إلى target؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
ابدأ بـ
nums[0]. إذا كان اختيارك يتضمنه، فيجب أن تكوّن القيم الأخرىtarget-nums[0]. وإذا لم يكن كذلك، فيجب أن تكوّنtarget. كلاهما السؤال نفسه على مصفوفة أقصر.يعتمد ما إذا كانت القيم ابتداءً من الموضع
iقادرة على تكوين مجموعrعلىiوrفقط، ولا تتجاوز قيمةrأبدًاtarget. لذا يوجد نحو 200 × 10^4 سؤالًا مختلفًا على الأكثر، ويمكن الإجابة عن كل منها مرة واحدة.استخدم قيمة منطقية واحدة لكل مجموع من 0 إلى
target، مع جعل المجموع 0 وحده قابلًا للوصول في البداية. أضف القيم واحدة تلو الأخرى: يصبح المجموعsقابلًا للوصول إذا كانs-numقابلًا للوصول مسبقًا. حدّث المجاميع من الأعلى إلى الأدنى كيلا تُستخدم القيمة مرتين، واقرأ الإجابة عندtarget.
الحل
الاختيار هو نعم أو لا لكل قيمة، لذا فإن 200 قيمة تعطي 2^200 اختيارًا. لكن ما يهم هو المجاميع التي لا تتجاوز target ≤ 10^4. سجّل المجاميع التي يمكن للقيم حتى الآن تكوينها: كل قيمة جديدة تُزيح هذا السجل بمقدارها، ويصبح البحث جدولًا من قيم منطقية بأبعاد n × target.
اختر كل قيمة أو تخطَّها
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
تسأل canMake(i, remaining) عمّا إذا كانت القيم ابتداءً من الموضع i يمكنها أن تكوّن remaining بالضبط. خذ nums[i] إذا كان مناسبًا، وهذا يترك remaining-nums[i] للباقي؛ وإذا لم ينجح ذلك، فتجاوزه. كل اختيار يمثّل مسارًا واحدًا، لذا يعثر البحث على اختيار متى وُجد.
عندما لا يوجد أي اختيار، فإنه يمرّ عليها جميعًا. مع وجود 200 من مضاعفات العدد 3، لا يتجاوز أيٌّ منها 300، وهدف مقداره 9998، لا ينجح أي اختيار، ومع ذلك فإن أي 33 قيمة تبقى دون الهدف: أكثر من 10^37 مسارًا.
الخوارزمية
- اكتب
canMake(i, remaining). - تعني القيمة
remainingالتي تساوي 0 أن الاختيار اكتمل: أعد true. إذا لم تتبقَّ أي قيم وما زال هناك شيء مطلوب تكوينه، فأعد false. - إذا كان
nums[i] ≤ remainingوكانتcanMake(i+1, remaining-nums[i])تساوي true، فأعد true. - وإلا فأعد
canMake(i+1, remaining). - أعد
canMake(0, target).
def isSubsetSum(nums, target):
n = len(nums)
# Can some of nums[i], nums[i+1], ... add up to exactly remaining?
def can_make(i, remaining):
if remaining == 0:
return True
if i == n:
return False
if nums[i] <= remaining and can_make(i + 1, remaining - nums[i]):
return True # take nums[i]
return can_make(i + 1, remaining) # skip it
return can_make(0, target)املأ جدول المجاميع الممكن الوصول إليها
الفكرة
يعتمد الاستدعاء التكراري فقط على موضع ومجموع متبقٍ بين 0 وtarget، وتصل مسارات كثيرة إلى الزوج نفسه. املأ جدولًا بدلًا من ذلك. تكون made[i][s] true عندما يكون مجموع اختيار من أول i قيمة مساويًا تمامًا لـs؛ والاختيار الفارغ يجعل المجموع 0. مع num = nums[i-1]، يكون المجموع s ممكنًا إذا كان ممكنًا دون num، أي made[i-1][s]، أو إذا أكمل num المجموع s-num، أي made[i-1][s-num] عندما يكون s ≥ num.
في المثال الأول، بعد العدد 8 تكون المجاميع الممكنة 0 و8. يضيف العدد 3 المجموعين 3 و11، ولا يضيف العدد 11 سوى 14، ويضيف العدد 5 المجموعين 5 و13، ويصل 8 + 7 إلى 15. عند الحدود القصوى، يحتوي الجدول على 201 × 10001 خلية، أي نحو 2 × 10^6 خطوة.
الخوارزمية
- هيّئ
madeعلى شكل n+1 صفوف وtarget+1 قيمة منطقية، جميعها false. واجعلmade[0][0]true للاختيار الفارغ. - يتعامل الصف
iمع القيمةnum = nums[i-1]، حيثi= 1 إلى n. - لكل مجموع
sمن 0 إلىtarget، اجعلmade[i][s]مساويًا لـmade[i-1][s]. - إذا كان
s ≥ numوكانتmade[i-1][s-num]تساوي true، فاجعلmade[i][s]تساوي true. - أعِد
made[n][target].
def isSubsetSum(nums, target):
n = len(nums)
# made[i][s]: some of the first i values add up to exactly s
made = [[False] * (target + 1) for _ in range(n + 1)]
made[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 on top of a sum of s-num
made[i][s] = made[i - 1][s] or (s >= num and made[i - 1][s - num])
return made[n][target]صف واحد من عمليات الجمع، يُحدَّث من الأعلى
الفكرة
يقرأ كل صف الصف الذي قبله فقط، لذا يمكن لمصفوفة واحدة made[s] أن تحتوي عليه. حدّثها تصاعديًا، وستُستخدم القيمة نفسها لتكوين نفسها: مع nums = [5] والهدف 10، تصبح s = 5 صحيحة، ثم تقرأ s = 10 هذه الخانة المُحدَّثة حديثًا، مستخدمةً العدد 5 مرتين.
بدلًا من ذلك، انتقل من target نزولًا إلى num. ستصل القراءة عند s-num إلى خانة أصغر لم يُعِد المرور الكتابة فيها، لذا سترى الصف الذي كان موجودًا قبل num. يظل المجموع الذي أمكن تكوينه كذلك، لذا يمكنك التوقف بمجرد أن تصبح made[target] صحيحة. تنخفض الذاكرة إلى target + 1 قيمة منطقية.
الخوارزمية
- ابدأ بمصفوفة واحدة تحتوي على
target + 1قيمة منطقية، بحيث تكونmade[0]وحدها true. - تناول القيم بالترتيب. لكل
num، أنقصsمنtargetحتىnum. - كلما كانت
made[s-num]تحمل القيمة true، عيّنmade[s]إلى true. - توقّف وأعد
trueفور تعيينmade[target]إلى true. - إذا استُخدمت كل القيم أولًا، فالإجابة هي
false.
def isSubsetSum(nums, target):
# made[s]: some of the values seen so far add up to exactly s
made = [False] * (target + 1)
made[0] = True
for num in nums:
# Downward, so made[s - num] still ignores num
for s in range(target, num - 1, -1):
if made[s - num]:
made[s] = True
if made[target]:
return True
return False
أخطاء شائعة وحالات حدّية
- تستخدم الحلقة التصاعدية على المجاميع قيمةً مرتين:
[3]مع الهدف 9 تعطي الإجابة true. - نسيان
made[0] = true. يُبنى كل مجموع انطلاقًا من الاختيار الفارغ، لذا تكون كل الإجابات false. - اختيار أكبر القيم أولًا. في
[6, 5, 5]مع الهدف 10، يؤدي أخذ 6 إلى بقاء 4، وهو ما لا يمكن تكوينه، بينما 5 + 5 = 10. - القيمة التي تتجاوز
target، كما في[10000]مع الهدف 1، يجب ألا تغيّر شيئًا. يوقفnum...targetفي Swift البرنامج، ويعدّ(num+1):(target+1)في R تنازليًا، لذا تحقّق أولًا منnum ≤ target. - في Lua وR، يقع الإدخال الخاص بالمجموع
sعند الفهرسs + 1.
أسئلة شائعة4
ما التعقيد الزمني لمسألة مجموع المجموعات الجزئية؟
يستغرق الجدول زمنًا قدره O(n × target)، أي نحو 2 × 10^6 خطوة لـ 200 قيمة وهدف مقداره 10^4، ويقلل استخدام صف واحد الذاكرة إلى O(target). تتناسب الكلفة مع الحجم العددي للهدف، لذا فالطريقة شبه متعددة الحدود ولا تصلح لهدف مثل 10^18. عمومًا، مشكلة مجموع المجموعات الجزئية NP-complete.
ما العلاقة بين مسألة مجموع المجموعة الجزئية ومسألة تقسيم المجموعة إلى مجموعتين فرعيتين متساويتَي المجموع ومسألة حقيبة الظهر 0/1؟
مشكلة تقسيم المجموع إلى مجموعتين متساويتين هي مسألة المجموع الجزئي مع target = total / 2، بعد التحقق من أن المجموع زوجي. المجموع الجزئي هو مسألة حقيبة ظهر 0/1، حيث تكون قيمة كل عنصر هي وزنه، ويجب ملء الحقيبة تمامًا، لذا يحتوي الجدول على قيم منطقية بدلًا من القيم المثلى.
هل تعمل مسألة مجموع المجموعة الجزئية مع الأعداد السالبة؟
الفكرة صحيحة، لكن الشيفرة أعلاه لا تعمل. عند وجود أعداد سالبة، تمتد المجاميع الممكن الوصول إليها من مجموع الأعداد السالبة إلى مجموع الأعداد الموجبة، لذا أزِح كل فهرس بمقدار ذلك المجموع الأدنى واملأ الصف بالطريقة نفسها. لم يعد من الممكن تخطي قيمة أكبر من المجموع المتبقي.
كيف تعرف القيم التي تحقق الهدف؟
احتفظ بالجدول كاملًا وابدأ عند made[n][target]. اصعد صفًا واحدًا في كل مرة: إذا كانت made[i-1][s] صحيحة، فهذا يعني أن nums[i-1] لم تكن مطلوبة؛ وإلا فسجّلها واطرحها من s. توقّف عند المجموع 0 بعد اختيار عنصر صالح.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def isSubsetSum(nums, target):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
nums = [8, 3, 11, 5, 7] target = 15
الإخراج المتوقع
true