Partition Equal Subset Sum

Q: لماذا تُعدّ مسألة تقسيم المجموعة إلى مجموعتين متساويتَي المجموع مسألة حقيبة ظهر 0/1؟

لديك حقيبة بسعة target = total / 2 ويجب ملؤها تمامًا، مع استخدام كل قيمة مرة واحدة على الأكثر. اختيار قيمة أو تركها هو خيار 0/1، وحجم القيمة هو قيمتها نفسها. يجيب جدول الحقيبة للمجاميع الممكنة عن ذلك في زمن O(n × target).

Q: ما هو التعقيد الزمني لمسألة تقسيم مجموعة فرعية إلى مجموعتين متساويتين في المجموع؟

يستغرق أسلوب الجدول زمنًا قدره O(n × target)، حيث إن target يساوي نصف المجموع الكلي، ويستهلك ذاكرة قدرها O(target) باستخدام صف واحد. مع 200 قيمة لا تتجاوز 100، يكون ذلك نحو 2 × 10^6 خطوة. يزداد الحد مع حجم القيم، وليس مع عددها فقط، لذا يُسمى شبه كثير الحدود: عند وجود قيم تقارب 10^9، لن يتسع لها أي جدول، والمسألة العامة NP-complete.

Q: لماذا تنتقل الحلقة الداخلية من الهدف نزولًا إلى القيمة؟

يعني التكرار التنازلي أن reach[s-num] تُقرأ قبل أن تتمكن هذه القيمة من تغييرها، لذا فهي لا تزال تصف القيم قبل num . أما التكرار التصاعدي فيسمح بتمديد مجموع بُني باستخدام num بإضافة num إليه مرة أخرى، ما يؤدي إلى احتساب قيمة واحدة عدة مرات. التكرار التصاعدي هو الخيار الصحيح عند السماح بعدد غير محدود من النسخ، كما في Coin Change، لكنه الخيار الخاطئ هنا.

متوسطالبرمجة الديناميكية

+10

لديك مصفوفة nums من أعداد صحيحة موجبة. حدّد ما إذا كان بإمكانك تقسيم القيم إلى مجموعتين متساويتين في مجموعهما. يجب أن تنتمي كل قيمة إلى مجموعة واحدة فقط، ويمكن للمجموعة أن تضم قيماً من أي مواضع. أعد true إذا وُجد مثل هذا التقسيم، وfalse خلاف ذلك.

الدالة

canPartition(nums: integer-array) → boolean

numsinteger-array: القيم الموجبة لتقسيمها إلى مجموعتين
تُرجعboolean: صحيح عندما يمكن تقسيم القيم إلى مجموعتين متساويتين في المجموع، وخطأ خلاف ذلك

القيود

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 100

أمثلة

المدخلات: nums = [6, 1, 4, 9, 2]
المخرجات: true
الشرح: المجموع هو 22، لذا تحتاج كل مجموعة إلى 11. المجموعتان 9 + 2 و6 + 1 + 4 تساوي كلٌّ منهما 11، لذا الإجابة هي true.

المدخلات: nums = [4, 7, 2, 9, 6]
المخرجات: false
الشرح: المجموع هو 28، لذا تحتاج كل مجموعة إلى 14. المجموعة التي تضم 9 تحتاج إلى 5 أخرى، ولا توجد أي مجموعة من 4 و7 و2 و6 مجموعها 5، لذا فالإجابة هي false رغم أن المجموع زوجي.

المدخلات: nums = [1, 2, 3, 5]
المخرجات: false
الشرح: المجموع هو 11. مجموع عددين صحيحين متساويين يكون دائمًا عددًا زوجيًا، لذلك لا يمكن أبدًا تقسيم مجموع فردي، والإجابة هي false.

+18 اختبارات مخفية عند الإرسال

سؤال إضافي

عندما لا يوجد تقسيم متساوٍ، هل يمكنك إرجاع أصغر فرق ممكن بين مجموعَي المجموعتين؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

يجب أن تحتوي كل مجموعة على نصف المجموع الكلي تمامًا، لذا فالسؤال الحقيقي هو ما إذا كانت هناك مجموعة جزئية من nums يكون مجموعها target = total / 2. تتطلب تجربة كل المجموعات الجزئية 2^n، وهذا غير عملي عند وجود 200 قيمة. لكن المجاميع نفسها صغيرة: إذ لا تتجاوز target القيمة 200 × 100 / 2 = 10^4. إن تسجيل المجاميع الممكن الوصول إليها، قيمةً تلو الأخرى، يحوّل البحث إلى جدول لحقيبة ظهر 0/1 يُملأ في O(n × sum) خطوة.

جرّب كل مجموعة جزئية باستخدام الاستدعاء الذاتي

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

ابدأ بالمجموع الكلي. إذا كان فرديًا، فلا يوجد تقسيم، لأن مجموع عددين صحيحين متساويين يكون عددًا زوجيًا. وإلا، فيجب أن تساوي قيمة كل مجموعة بالضبط target = total / 2. وبمجرد أن تجد قيمًا تكوّن target، فإن القيم التي لم تخترها تكوّن النصف الآخر وحدها. لذا يكفي طرح سؤال واحد: هل توجد مجموعة فرعية يصل مجموعها إلى target؟

مرّ على القيم بالترتيب واتخذ خيارًا واحدًا لكل منها: ضعها في المجموعة الأولى، أو اتركها للثانية. تُجيب الدالة المساعدة reach(i, remaining) عمّا إذا كانت القيم ابتداءً من الفهرس i قادرة على تكوين remaining. وتُعيد true عندما تصبح قيمة remaining مساوية لـ 0، وfalse عندما تنفد القيم أو تصبح أقل من 0، وإلا فإنها تجرّب كلا الخيارين لـ nums[i].

كل مجموعة فرعية تمثل مسارًا من الخيارات، لذا لا يمكن للبحث أن يفوّت أي تقسيم، وتكون الإجابة صحيحة. لكنه بطيء لأن هناك 2^n مسارًا، والمدخل الذي لا يقبل التقسيم يجبره على تجربة كل المسارات تقريبًا. خذ 199 نسخة من 100 ونسخة واحدة من 98: المجموع هو 19998، ولا تصل قيمة الهدف 9999 أبدًا، ويجرّب البحث كل الطرق الممكنة لاختيار 99 نسخة أو أقل من المئات، أي نحو 4 × 10^59 مسارًا. حتى 40 قيمة تعطي 2^40، أي نحو 10^12 مسارًا.

الخوارزمية

اجمع قيم nums. إذا كان المجموع فرديًا، فأعِد false.
عيّن target إلى نصف المجموع.
اكتب reach(i, remaining): أعِد true عندما تكون remaining تساوي 0، وfalse عندما تكون i بعد آخر قيمة أو تكون remaining أقل من 0.
وإلا فأعِد reach(i+1, remaining-nums[i]) أو reach(i+1, remaining): خذ القيمة أو اتركها.
أعِد reach(0, target).

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False

    # Can some of the values from index i on add up to exactly remaining?
    def reach(i, remaining):
        if remaining == 0:
            return True
        if i == len(nums) or remaining < 0:
            return False
        # Put nums[i] in the first group, or leave it for the second one
        return reach(i + 1, remaining - nums[i]) or reach(i + 1, remaining)

    return reach(0, total // 2)

املأ جدولًا بالقيمة والمجموع

الفكرة

يطرح الاستدعاء التكراري السؤال نفسه مرارًا وتكرارًا. تعتمد reach(i, remaining) على عددين فقط: i من 0 إلى n وremaining من 0 إلى target. وهذا يعني وجود ما لا يزيد على (n+1) × (target+1) سؤالًا مختلفًا، أي نحو 201 × 10001 ≈ 2 × 10^6 عند الحدود القصوى، وهو عدد قليل بما يكفي للإجابة عن كل سؤال مرة واحدة.

ابنِ الإجابات تصاعديًا في جدول. تشير can[i][s] إلى إمكانية أن يكون مجموع بعض القيم i الأولى مساويًا لـ s. عند عدم وجود أي قيم، يكون المجموع 0 وحده ممكنًا، لذا يكون الصف 0 بقيمة false باستثناء can[0][0]. تتيح القيمة num = nums[i-1] طريقتين للوصول إلى s: إما استبعاد num، بحيث تكون القيم السابقة قد وصلت بالفعل إلى s، أو تضمينها، بحيث تصل القيم السابقة إلى s-num. هذه هي القاعدة كاملة: can[i][s] = can[i-1][s] or can[i-1][s-num]، حيث لا يُحتسب الجزء الثاني إلا عندما تكون s ≥ num. يقرأ كل صف القيم من الصف الذي فوقه فقط، لذا تُستخدم كل قيمة مرة واحدة كحد أقصى.

مع [6, 1, 4, 9, 2] والهدف 11، تتسع المجاميع الممكنة من {0} إلى {0, 6}، ثم {0, 1, 6, 7}، ثم {0, 1, 4, 5, 6, 7, 10, 11}. يظهر المجموع 11 بعد إضافة 4 (6 + 1 + 4)، وتحافظ الصفوف اللاحقة عليه. الإجابة هي can[n][target]. تتطلب كل خلية عملًا ثابتًا، لذا فإن الزمن والذاكرة كلاهما O(n × target).

الخوارزمية

أعِد false إذا كان المجموع فرديًا، واجعل target نصفه.
أنشئ جدولًا من n+1 صفوف وtarget+1 أعمدة، تكون جميع قيمه false، واجعل can[0][0] يساوي true.
لكل صف i من 1 إلى n، خذ num = nums[i-1].
لكل مجموع s من 0 إلى target، اجعل can[i][s] يساوي can[i-1][s] أو، عندما s ≥ num، can[i-1][s-num].
أعِد can[n][target].

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2
    n = len(nums)

    # can[i][s] is True when some of the first i values add up to s
    can = [[False] * (target + 1) for _ in range(n + 1)]
    can[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 and reach s - num with the values before it
            can[i][s] = can[i - 1][s] or (s >= num and can[i - 1][s - num])
    return can[n][target]

صفّ واحد من عمليات الجمع، يُملأ من الأعلى إلى الأسفل

الفكرة

يقرأ كل صف في الجدول الصف الذي فوقه فقط، لذا يكفي صف واحد إذا حدّثته في مكانه: يحدّد reach[s] ما إذا كان مجموع بعض القيم التي ظهرت حتى الآن يساوي s. يكمن الخطر في ترتيب التحديثات. إذا مررت على s تصاعديًا، فربما يكون reach[s-num] قد فُعّل بالفعل باستخدام num نفسه. مع [3, 9] والهدف 6، تجعل القيمة 3 من reach[3] صحيحًا، ثم تقرأه لتجعل reach[6] صحيحًا، وكأن لديك قيمتين 3، فتجيب بصحيح عن تقسيم غير موجود.

مرّر على s تنازليًا، من target إلى num. عندها يكون s-num فهرسًا أصغر لم تلمسه هذه القيمة بعد، لذا يظل reach[s-num] محتفظًا بالإجابة من قبل وصول num. وهذا يطابق تمامًا can[i-1][s-num] في الجدول، ويؤدي الصف الواحد عمل الجدول كله.

يمكنك أيضًا التوقف فور أن تصبح reach[target] صحيحة، لأن القيم اللاحقة لا تفعل سوى إضافة مجاميع يمكن الوصول إليها ولا تزيل أيًا منها. تظل الحالة الأسوأ تتطلب O(n × target) خطوة، أي نحو 2 × 10^6، وتنخفض الذاكرة إلى target + 1 قيمة منطقية.

الخوارزمية

أعِد false إذا كان المجموع فرديًا، واجعل target نصفه.
أنشئ reach بعدد خانات يساوي target + 1، واجعلها كلها false باستثناء reach[0].
لكل قيمة num، مرّ على s تنازليًا من target إلى num، واجعل reach[s] تساوي true عندما تكون reach[s-num] تساوي true.
بعد كل قيمة، أعد true إذا كانت reach[target] تساوي true.
إذا انتهت الحلقة، فأعد reach[target]، وهي false.

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2

    # reach[s] is True when some of the values seen so far add up to s
    reach = [False] * (target + 1)
    reach[0] = True
    for num in nums:
        # Walk the sums downward so num is used at most once
        for s in range(target, num - 1, -1):
            if reach[s - num]:
                reach[s] = True
        if reach[target]:
            return True
    return reach[target]

أخطاء شائعة وحالات حدّية

تأتي الإجابات الخاطئة هنا من الوثوق بقاعدة جشعة، وتجاوز فحص الأعداد الفردية، وإعادة استخدام قيمة في الجدول ذي الصف الواحد.

إن السير عبر المجاميع تصاعديًا في النسخة ذات الصف الواحد يستخدم القيمة أكثر من مرة. مع [3, 9] يكون الهدف 6، وتُعلِّم القيمة 3 المجموع 3 ثم المجموع 6، فتجيب بصحيح.
تجاوز فحص الأعداد الفردية: بالنسبة إلى [1, 2]، يُقرَّب المجموع 3 إلى الأسفل ليصبح الهدف 1، وتصل إليه القيمة 1، فتجيب بصحيح عن تقسيم لا يمكن أن يوجد.
يفشل التوزيع الجشع، مثل الترتيب ثم الإضافة دائمًا إلى المجموعة الأخف، مع [3, 3, 2, 2, 2]: إذ ينتهي عند 7 مقابل 5، بينما 3 + 3 = 2 + 2 + 2.
قيمة أكبر من الهدف، كما في [2, 2, 2, 10]. عندها تنفّذ حلقة تنازلية من target إلى num صفر مرة، وهذا صحيح، لكن نطاقًا مثل (num+1):(target+1) في R يعدّ تنازليًا ويُفسد الجدول. تخطَّ مثل هذه القيم.
كون المجموع زوجيًا لا يكفي: فمجموع [4, 7, 2, 9, 6] يساوي 28، ومع ذلك لا يوجد تقسيم.
تبدأ المصفوفات في Lua وR من 1، لذا يقع الإدخال الخاص بالمجموع s عند الفهرس s + 1.

أسئلة شائعة4

لماذا تُعدّ مسألة تقسيم المجموعة إلى مجموعتين متساويتَي المجموع مسألة حقيبة ظهر 0/1؟

لديك حقيبة بسعة target = total / 2 ويجب ملؤها تمامًا، مع استخدام كل قيمة مرة واحدة على الأكثر. اختيار قيمة أو تركها هو خيار 0/1، وحجم القيمة هو قيمتها نفسها. يجيب جدول الحقيبة للمجاميع الممكنة عن ذلك في زمن O(n × target).

ما هو التعقيد الزمني لمسألة تقسيم مجموعة فرعية إلى مجموعتين متساويتين في المجموع؟

يستغرق أسلوب الجدول زمنًا قدره O(n × target)، حيث إن target يساوي نصف المجموع الكلي، ويستهلك ذاكرة قدرها O(target) باستخدام صف واحد. مع 200 قيمة لا تتجاوز 100، يكون ذلك نحو 2 × 10^6 خطوة. يزداد الحد مع حجم القيم، وليس مع عددها فقط، لذا يُسمى شبه كثير الحدود: عند وجود قيم تقارب 10^9، لن يتسع لها أي جدول، والمسألة العامة NP-complete.

لماذا تنتقل الحلقة الداخلية من الهدف نزولًا إلى القيمة؟

يعني التكرار التنازلي أن reach[s-num] تُقرأ قبل أن تتمكن هذه القيمة من تغييرها، لذا فهي لا تزال تصف القيم قبل num. أما التكرار التصاعدي فيسمح بتمديد مجموع بُني باستخدام num بإضافة num إليه مرة أخرى، ما يؤدي إلى احتساب قيمة واحدة عدة مرات. التكرار التصاعدي هو الخيار الصحيح عند السماح بعدد غير محدود من النسخ، كما في Coin Change، لكنه الخيار الخاطئ هنا.

هل يمكن حل مسألة تقسيم المصفوفة إلى مجموعتين متساويتين باستخدام مجموعة بتات؟

نعم. خزّن المجاميع الممكنة الوصول إليها على شكل بتات في عدد كبير واحد، مع ضبط البت 0 فقط في البداية. لكل قيمة، تضيف bits |= bits << num تلك القيمة إلى كل مجموع ممكن الوصول إليه دفعة واحدة، وتكون الإجابة هي ما إذا كان البت target مضبوطًا. هذا هو الجدول نفسه، لكن كل كلمة آلة تتعامل مع 64 مجموعًا في المرة الواحدة، لذا يعمل عمليًا بسرعة أكبر بكثير.

Python

def canPartition(nums):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

nums = [6, 1, 4, 9, 2]

المتوقع

true

Partition Equal Subset Sum

الدالة

القيود

أمثلة

تلميحات

الحل

جرّب كل مجموعة جزئية باستخدام الاستدعاء الذاتي

املأ جدولًا بالقيمة والمجموع

صفّ واحد من عمليات الجمع، يُملأ من الأعلى إلى الأسفل

أخطاء شائعة وحالات حدّية

أسئلة شائعة4

مسائل مشابهة