Combination Sum

Q: لماذا تستدعي الدالة نفسها باستخدام i وليس i + 1 في مسألة مجموع التركيبات؟

يتيح الاستدعاء الذاتي باستخدام i أن تكون القيمة التالية هي المرشح نفسه مرة أخرى، وهذه هي الطريقة التي تتيح استخدام قيمة أكثر من مرة. أما الاستدعاء الذاتي باستخدام i + 1 فيتجاوز هذا المرشح، ما يحوّل المسألة إلى الصيغة التي يُستخدم فيها كل مرشح مرة واحدة على الأكثر. والجزء الآخر من القاعدة مهم بالقدر نفسه: عدم الرجوع أبدًا إلى فهرس يسبق i يُبقي كل مجموعة بالترتيب التصاعدي ويمنع التكرارات.

متوسطالتراجع

+10

لديك قائمة candidates تضم أعدادًا صحيحة موجبة مختلفة، وعددًا صحيحًا موجبًا target. أوجد كل تركيبة من عناصر القائمة يكون مجموع قيمها مساويًا تمامًا لـ target، مع إمكانية استخدام كل عنصر أي عدد من المرات. تُعد تركيبتان متماثلتين إذا استخدمتا القيم نفسها العدد نفسه من المرات، لذا تُحتسب [2, 3, 3] و[3, 2, 3] مرة واحدة.

أعِد كل تركيبة بحيث تكون قيمها بترتيب تصاعدي، ورتّب التركيبات ترتيبًا معجميًا: قارن بين تركيبتين قيمةً قيمةً من اليسار، وتأتي أولًا التركيبة التي تحتوي على القيمة الأصغر عند أول موضع اختلاف.

الدالة

combinationSum(candidates: integer-array, target: integer) → integer-2d-array

candidatesinteger-array: القيم المختلفة التي يمكنك استخدامها، بأي ترتيب، وبالعدد الذي تريده من المرات
targetinteger: يجب أن يصل مجموع كل تركيبة إلى القيمة المحددة تمامًا
تُرجعinteger-2d-array: كل مجموعة من العناصر التي يكون مجموعها مساويًا للهدف، مع ترتيب عناصر كل مجموعة تصاعديًا، ثم إدراج المجموعات بترتيب معجمي

القيود

1 ≤ candidates.length ≤ 50
2 ≤ candidates[i] ≤ 500
2 ≤ target ≤ 500
جميع القيم في candidates مختلفة، وليس لها ترتيب محدد.
تصل مجموعة واحدة على الأقل إلى target، ولا يزيد عدد المجموعات التي تصل إليه على 150.

أمثلة

المدخلات: candidates = [6, 2, 3]target = 8
المخرجات: [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
الشرح: أربعة أعداد 2 تساوي 8، وكذلك 2 + 3 + 3 و2 + 6. تبدأ الحالات الثلاث كلها بالعدد 2، لذا تحدد القيمة الثانية الترتيب: 2، ثم 3، ثم 6. من دون 2، لا يبقى لديك سوى أعداد 3 و6، وكل مزيج منها هو مضاعف للعدد 3، بينما 8 ليس كذلك.

المدخلات: candidates = [5, 3, 4]target = 11
المخرجات: [[3, 3, 5], [3, 4, 4]]
الشرح: كلٌّ من 3 + 3 + 5 و3 + 4 + 4 يساوي 11. يتطابقان عند القيمة الأولى، وعند القيمة الثانية يكون 3 أصغر من 4، لذا تأتي [3, 3, 5] أولًا. لا توجد أي تركيبة من 4ات و5ات فقط تساوي 11.

المدخلات: candidates = [4, 9]target = 9
المخرجات: [[9]]
الشرح: العدد 9 بمفرده تركيبة. لا تعطينا الأربعات إلا 4 و8 و12 في طريقها إلى ما بعد 9، و4 + 9 يساوي بالفعل 13، لذا فإن [9] هو الجواب الوحيد.

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

سؤال إضافي

يمكن الآن استخدام كل مرشح مرة واحدة على الأكثر، وقد تحتوي candidates على قيم مكررة. كيف تغيّر البحث بحيث لا يظهر أي تركيب مرتين؟

تلميحات

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

فُتح 0 من 3

الحل

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

جرّب كل عدد لكل مرشّح

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

الفكرة

يُوصَف كل تركيب بالكامل بعدد النسخ التي يستخدمها من كل عنصر مرشح. بالنسبة إلى [6, 2, 3] والهدف 8، فإن الإجابة [2, 3, 3] تتكون من 2 واحد و3 مرتين، ولا تحتوي على 6. لذا فإن إحدى طرق العثور على كل الإجابات هي تجربة كل عدد ممكن من النسخ لكل عنصر مرشح، والاحتفاظ بالخيارات التي يساوي مجموعها target تمامًا. يمكن استخدام العنصر المرشح c بحد أقصى target / c مرة، لذا يتراوح عدده من 0 إلى ذلك الحد.

تخيّل شجرة قرارات ذات مستوى لكل عنصر مرشح، بعد ترتيبها. عند المستوى i تقرر عدد نسخ القيمة ذات الفهرس i التي ستأخذها، وكل ورقة في الأسفل تمثل اختيارًا كاملًا للأعداد. لكل مجموعة متعددة العناصر قائمة أعداد واحدة بالضبط، لذا لن يُعثر على أي تركيب مرتين. كما أن تجربة العدد الأكبر أولًا تعطي الترتيب المطلوب: عندما تختلف إجابتان للمرة الأولى في عدد نسخ قيمة ما، تكون الإجابة التي تحتوي على نسخ أكثر ما تزال تحتفظ بتلك القيمة الصغيرة، بينما تحتوي الأخرى بالفعل على قيمة أكبر، لذا تأتي الأولى قبل الثانية.

المشكلة هي حجم الشجرة. عدد الأوراق هو حاصل ضرب target / c + 1 لجميع العناصر المرشحة: بالنسبة إلى [2, 3, 6] المرتبة والهدف 8، يكون الناتج 5 × 3 × 2 = 30 ورقة مقابل 3 إجابات. كل عنصر مرشح أكبر من target / 2 يضاعف عدد الأوراق، رغم أنه لا يمكن استخدامه إلا مرة واحدة كحد أقصى، لذا فإن 40 عنصرًا مرشحًا من هذا النوع وحدها تعني 2^40، أي نحو 10^12، ورقة. الاختبارات الكبيرة مصممة بهذه الطريقة، ولا يمكن لهذا النهج إنجازها.

الخوارزمية

رتّب العناصر المرشحة وأنشئ مصفوفة من الأعداد، عددًا واحدًا لكل قيمة.
اكتب choose(i, total)، التي تحدد عدد القيمة عند الفهرس i.
من أجل k، بدءًا من target / nums[i] نزولًا إلى 0، عيّن العدد إلى k واستدعِ choose(i + 1, total + k × nums[i]).
عندما يكون لكل قيمة عدد، احتفظ بالتركيبة إذا كان total يساوي target، مع كتابة كل قيمة بعدد مرات يساوي عددها.
استدعِ choose(0, 0). تكون التركيبات المحتفَظ بها مرتبة معجميًا بالفعل.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    counts = [0] * len(nums)
    result = []

    def choose(i, total):
        if i == len(nums):
            if total == target:
                combo = []
                for value, k in zip(nums, counts):
                    combo.extend([value] * k)
                result.append(combo)
            return
        # Most copies first, so the combinations come out in lexicographic order.
        for k in range(target // nums[i], -1, -1):
            counts[i] = k
            choose(i + 1, total + k * nums[i])
        counts[i] = 0

    choose(0, 0)
    return result

تراجع بترتيب تصاعدي مع التقليم

الفكرة

ابنِ كل تركيب بإضافة قيمة واحدة في كل مرة، بالطريقة التي ستدوّنه بها: بترتيب تصاعدي. يفرض مؤشر البداية هذا الترتيب. بعد وضع nums[i]، قد تكون القيمة التالية هي nums[i] مرة أخرى، لأن المرشح يمكن أن يتكرر، أو أي قيمة لاحقة، لكن ليس قيمة أسبق. لذا فإن الاستدعاء الذي وضع الفهرس i يكرّر الحلقة ابتداءً من i فقط. لكل تركيب ترتيب تصاعدي واحد بالضبط، لذا له مسار واحد بالضبط في الشجرة، ولا يُبنى مطلقًا تركيب مكرر مثل [3, 2, 3].

إليك الشجرة كاملةً للقائمة المرتبة [2, 3, 6] والهدف 8. لدى الجذر 8 متبقية، ويجرّب 2 و3 و6. تحت 2 يتبقى 6. وتحت 2، 2 يتبقى 4، وبعد 2، 2، 2 يتبقى 2، وإضافة 2 أخرى تحوّله إلى الإجابة [2, 2, 2, 2]؛ أما 2، 2، 3 فيتبقى بعده 1 وينتهي مساره. وتحت 2، 3 يتبقى 3، ويمكن تجربة 3 و6 فقط، وتؤدي إضافة 3 إلى [2, 3, 3]. وتحت 2، 6 لا يتبقى شيء: [2, 6]. وتحت 3 لا يمكن تجربة إلا 3 و6، وبعد 3، 3 يتبقى 2، وهو ما لا يكمّله أيٌّ منهما. وتحت 6 يتبقى 2، ولا يمكن تجربة إلا 6. مجموع الاستدعاءات اثنا عشر، مقابل 30 ورقة في النهج الأول.

يحوّل الفرز الطريق المسدود إلى توقّف مبكر. عندما تكون nums[i] أكبر من المتبقي، تكون كل قيمة لاحقة أكبر منها أيضًا، لذا تخرج من الحلقة باستخدام break بدلًا من اختبار بقية القيم. في الشجرة أعلاه، تفحص العقدة 2، 2، 3 التي يتبقى لها 1 القيمة 3، وترى أنها لا تناسب، ولا تفحص 6 مطلقًا. لا يزور البحث إلا البادئات التي لا يزال مجموعها لا يتجاوز target، ولهذا تستغرق الاختبارات الكبيرة التي تُجهد النهج الأول بضعة آلاف من الاستدعاءات هنا.

ينشأ ترتيب المخرجات من الاستكشاف نفسه. عند كل مستوى، تجرّب الحلقة القيم الأصغر أولًا، ويُكتب كل تركيب بترتيب تصاعدي. تختلف كل إجابتين أولًا عند المستوى الذي ينقسم فيه مسارهما، وقد جرى استكشاف المسار الذي يحمل القيمة الأصغر عندها أولًا، لذا تظهر الإجابات بترتيب معجمي. لا يمكن أن يكون أحد التركيبين بادئةً لتركيب آخر، لأن القيم موجبة وكلاهما يصل إلى المجموع نفسه.

الخوارزمية

رتّب المرشحين بترتيب تصاعدي.
اكتب backtrack(start, remaining) التي تشارك قائمة واحدة path. إذا كانت remaining تساوي 0، فاحفظ نسخة من path.
وإلا، فكرّر i من start إلى النهاية. إذا كان nums[i] > remaining، فتوقّف: كل قيمة لاحقة أكبر.
أضف nums[i]، واستدعِ backtrack(i, remaining-nums[i]) باستخدام i، وليس i + 1، كي تتكرر القيمة، ثم أزِلها.
استدعِ backtrack(0, target) وأعِد التركيبات المحفوظة، المرتبة بالفعل ترتيبًا معجميًا.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break  # sorted, so every later value is too big as well
            path.append(nums[i])
            backtrack(i, remaining - nums[i])  # i, not i + 1: nums[i] may repeat
            path.pop()

    backtrack(0, target)
    return result

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

معظم الإجابات الخاطئة سببها ترتيب البحث، لا الحساب.

إنشاء حلقة تمرّ على كل مرشّح في كل مستوى، بدلًا من البدء بالفهرس الحالي، ينتج [2, 3, 3] و[3, 2, 3] و[3, 3, 2] بوصفها ثلاثة حلول. إن فرز كل حل وإزالة التكرارات بعد ذلك يعطي القائمة الصحيحة، لكنه يتطلب عملًا أكبر بمقدار أُسّي.
إن استدعاء الدالة递يًّا باستخدام i + 1 بدلًا من i يسمح بظهور كل قيمة مرة واحدة فقط، لذا يغيب [2, 2, 2, 2].
حفظ path نفسه بدلًا من نسخة منه: عندها تكون كل الإجابات المحفوظة القائمة نفسها، التي يكون التراجع قد أفرغها بحلول النهاية.
استخدام break مع مرشّحات لم تفرزها. مع [6, 2, 3] وبقاء 2، تتوقف الحلقة عند 6 ولا تجرّب 2 أبدًا.
إرجاع التركيبات بالترتيب الذي توحي به المدخلات غير المرتبة. القائمة المتوقعة مرتبة ترتيبًا معجميًا، ويعطيها البحث المرتب دون الحاجة إلى فرز إضافي.
في Lua وR، تبدأ المصفوفات من 1، لذا يبدأ الاستدعاء الأول عند الفهرس 1، وتمتد الحلقة حتى طول المصفوفة.

أسئلة شائعة4

ما هو التعقيد الزمني لمسألة مجموع التركيبات؟

البحث بالتراجع أُسّي. مع وجود n مرشحًا، والهدف t، وأصغر مرشح m، يحتوي كل تركيب على t/m قيمة كحد أقصى، ولكل خطوة n خيارات كحد أقصى، ما يحدّ العمل بـ O(n^(t/m)). ويؤدي التقليم باستخدام المرشحين المرتبين إلى إبقاء العدد الفعلي للاستدعاءات أقل بكثير من ذلك، لأن البحث لا يزور إلا البادئات التي لا يزال مجموعها لا يتجاوز t. والمساحة الإضافية هي O(t/m) للمسار الحالي ومكدس الاستدعاءات، بالإضافة إلى المخرجات.

لماذا تستدعي الدالة نفسها باستخدام i وليس i + 1 في مسألة مجموع التركيبات؟

يتيح الاستدعاء الذاتي باستخدام i أن تكون القيمة التالية هي المرشح نفسه مرة أخرى، وهذه هي الطريقة التي تتيح استخدام قيمة أكثر من مرة. أما الاستدعاء الذاتي باستخدام i + 1 فيتجاوز هذا المرشح، ما يحوّل المسألة إلى الصيغة التي يُستخدم فيها كل مرشح مرة واحدة على الأكثر. والجزء الآخر من القاعدة مهم بالقدر نفسه: عدم الرجوع أبدًا إلى فهرس يسبق i يُبقي كل مجموعة بالترتيب التصاعدي ويمنع التكرارات.

كيف تتجنب التركيبات المكررة دون استخدام مجموعة؟

أنشئ كل تركيبة بترتيب ثابت تصاعدي. يفرض فهرس البداية هذا الترتيب: بعد وضع nums[i]، لا يبحث الاستدعاء إلا في nums[i] والقيم اللاحقة. وهكذا يكون لكل تركيبة مسار واحد بالضبط في شجرة البحث، فتُنتَج مرة واحدة، ولا حاجة إلى مجموعة أو إزالة للتكرارات في النهاية.

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

نعم. احتفظ، لكل مجموع من 0 إلى الهدف، بقائمة التركيبات التي توصلك إليه، وأضف مرشحًا واحدًا في كل مرة كي تبقى القيم في كل قائمة مرتبة تصاعديًا، وهي الفكرة نفسها المستخدمة في حساب طرق تكوين مبلغ من العملات. لا يستكشف هذا الأسلوب طريقًا مسدودًا أكثر من مرة، لكنه يخزّن كل تركيبة جزئية لكل مجموع، ما يستهلك ذاكرة أكبر بكثير مما يستهلكه الاسترجاع، وقد تحتاج القائمة النهائية إلى الفرز. وبما أن حجم الناتج نفسه قد يكون أُسّيًا، فالاسترجاع هو الخيار المعتاد.

Python

def combinationSum(candidates, target):
    # اكتب الكود هنا

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

الحالة 1

الحالة 2

الحالة 3

المدخلات

candidates = [6, 2, 3]
target = 8

المتوقع

[[2, 2, 2, 2], [2, 3, 3], [2, 6]]