Combination Sum

Q: ما التعقيد الزمني لمسألة Combination Sum؟

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

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

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

Q: هل يمكن حل مسألة Combination Sum باستخدام البرمجة الديناميكية؟

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

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

+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، و2 + 3 + 3، و2 + 6، كلها تساوي 8، مرتبة حسب قيمتها الثانية. من دون 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, 3, 5] أولًا لأن قيمتها الثانية، 3، أصغر من 4. ولا توجد أي مجموعة من 4ات و5ات فقط تساوي 11.

سؤال إضافي

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

تلميحات

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

فُتح 0 من 3

الحل

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

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

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

الفكرة

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

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

الخوارزمية

رتّب المرشحين واحتفظ بعدد واحد لكل قيمة.
في choose(i, total)، جرّب كل عدد k من target / nums[i] تنازليًا حتى 0، واستدعِ 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] مرة أخرى أو أي قيمة لاحقة، ولا تكون أبدًا قيمة سابقة. لكل مجموعة ترتيب تصاعدي واحد بالضبط، لذا لها مسار واحد بالضبط، ولا يتم أبدًا تكوين [3, 2, 3].

بالنسبة إلى [2, 3, 6] المرتبة والهدف 8، تصل المسارات 2, 2, 2, 2 و2, 3, 3 و2, 6 إلى 8. يترك المسار 2, 2, 3 القيمة 1 ويتوقف من دون النظر إلى 6، ويترك المسار 3, 3 القيمة 2، التي لا تلائمها أي قيمة. هذا يعني 12 استدعاءً مقابل 30 ورقة في أسلوب العد.

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

الخوارزمية

رتّب المرشحين.
في backtrack(start, remaining)، احفظ نسخة من path المشتركة عندما تكون قيمة remaining هي 0.
وإلا، كرّر i بدءًا من start. إذا كان nums[i] > remaining، فتوقّف: كل قيمة لاحقة أكبر.
أضف nums[i]، واستدعِ backtrack(i, remaining - nums[i])، ثم أزله.
استدعِ 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 أبدًا.

أسئلة شائعة3

ما التعقيد الزمني لمسألة Combination Sum؟

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

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

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

هل يمكن حل مسألة Combination Sum باستخدام البرمجة الديناميكية؟

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

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

اختبار #1

اختبار #2

اختبار #3

الوسائط

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

الإخراج المتوقع

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