Target Sum

Q: ما علاقة مسألة المجموع المستهدف بمسألة مجموع المجموعة الجزئية؟

يجب أن يكون مجموع الأعداد ذات الإشارة الموجبة مساويًا لـ (S + target) / 2 ، لذا فإن الإجابة هي عدد المجموعات الجزئية من nums التي يكون مجموعها كذلك. تحلّ أي خوارزمية برمجة ديناميكية لعدّ مجاميع المجموعات الجزئية هذه المسألة بعد إضافة شرطين: أن تكون القيمة عددًا صحيحًا، وألا تتجاوز |target| القيمة S .

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

تعمل برمجة عدّ المجموعات الجزئية الديناميكية في زمن O(n × S) وباستخدام ذاكرة O(S) ، حيث إن S هو مجموع nums . ويستغرق الاستدعاء التعاودي مع التخزين المؤقت الزمن نفسه، لكنه يستخدم جدولًا بأبعاد n × (2S+1) . وتجربة كل إشارة تستغرق O(2^n) .

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

+10

لديك مصفوفة nums من أعداد صحيحة غير سالبة، وعدد صحيح target. ضع علامة زائد أو ناقص أمام كل عدد، مع الحفاظ على ترتيبها، ثم احسب قيمة التعبير. أعد عدد اختيارات العلامات التي تجعل قيمة التعبير تساوي target. يُحتسب كل اختيار من الاختيارات 2^n على حدة، لذا يُعدّ +0 و-0 اختيارين مختلفين.

الدالة

findTargetSumWays(nums: integer-array, target: integer) → integer

numsinteger-array: الأعداد، التي يحصل كلٌّ منها على إشارة
targetinteger: القيمة التي يجب أن يساويها التعبير
تُرجعinteger: عدد اختيارات الإشارات التي يساوي تعبيرها الهدف

القيود

1 ≤ nums.length ≤ 20
0 ≤ nums[i] ≤ 1000
مجموع nums لا يتجاوز 1000.
-1000 ≤ target ≤ 1000
الإجابة على الأكثر 2²⁰، وهي أقل بكثير من الحد الأقصى لعدد صحيح موقّع من 32 بت.

أمثلة

المدخلات: nums = [2, 1, 1]target = 2
المخرجات: 2
الشرح: +2 +1 -1 و+2 -1 +1 كلاهما يساوي 2. مع وضع إشارة ناقص على العدد 2، فإن أكبر قيمة يمكنك الوصول إليها هي -2 + 1 + 1 = 0، لذا لا ينجح أي خيار آخر.

المدخلات: nums = [0, 4, 4]target = 0
المخرجات: 4
الشرح: يجب أن تكون إشارَتا العددين 4 متعاكستين، +4 -4 أو -4 +4، وفي كلتا الحالتين يمكن أن تكون إشارة 0 موجبة أو سالبة. وهذا يعطي 2 × 2 = 4 اختيارات.

سؤال إضافي

هل يمكنك التعامل مع ما يصل إلى 40 عددًا، بقيم تصل إلى 10^9، عندما لا تتسع الذاكرة لأي مصفوفة مفهرسة بالمجموع؟

تلميحات

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

فُتح 0 من 3

الحل

لكل عدد إشارتان، لذا هناك 2^n تعبيرًا. يؤدي العد حسب الموضع والمجموع الجاري إلى دمج بادئات الإشارات التي تصل إلى المجموع نفسه. والأفضل من ذلك أن الأعداد ذات الإشارة الموجبة تشكّل مجموعة جزئية ذات مجموع ثابت، لذا تتحول المسألة إلى عدّ المجموعات الجزئية التي لها مجموع محدد، في زمن O(n × S) حيث S هو مجموع nums.

جرّب كلا الإشارتين لكل عدد

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

الفكرة

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

وهذا يعني ورقة واحدة لكل اختيار: 2^20 ≈ 10^6 ورقة لـ20 عددًا، وكل عدد إضافي يضاعف العمل.

الخوارزمية

اكتب count(i, total)، وهو عدد الطرق لإسناد الإشارات إلى nums[i..] عندما يكون مجموع الأعداد التي تسبق i هو total.
إذا كان i == n، فأعِد 1 عندما يكون total == target، وإلا فأعِد 0.
وإلا فأعِد count(i+1, total + nums[i]) + count(i+1, total - nums[i]).
الإجابة هي count(0, 0).

def findTargetSumWays(nums, target):
    n = len(nums)

    def count(i, total):
        # Ways to sign nums[i:] so that the whole expression ends at target
        if i == n:
            return 1 if total == target else 0
        return count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])

    return count(0, 0)

احفظ النتائج مؤقتًا حسب الموضع والمجموع الجاري

الفكرة

تعتمد count(i, total) فقط على i وtotal، وليس على الإشارات التي أدّت إلى المجموع. مع nums = [1, 1, 1, 1]، يصل كلٌّ من البادئتين +1 -1 و-1 +1 إلى المجموع 0 عند الموضع 2، لذا يكون البحث من هناك متماثلًا. خزّن كل نتيجة عند حسابها لأول مرة وأعِد استخدامها.

يبقى المجموع الجاري بين -S وS، لذا أزِحه بمقدار S لاستخدامه فهرسًا: memo[i][total + S]. يوجد على الأكثر n × (2S+1) حالة، أي نحو 4 × 10^4 حالة لـ20 عددًا مجموعها 1000، مع عمل ثابت لكل حالة.

الخوارزمية

احسب S = sum(nums) وأنشئ مصفوفة ذاكرة مؤقتة بحجم n × (2S+1)، واملأها بـ -1.
في count(i, total)، أعد الحالة الأساسية عند i == n كما سبق.
إذا كانت memo[i][total + S] تساوي -1، فاملأها بـ count(i+1, total + nums[i]) + count(i+1, total - nums[i]).
أعِد القيمة المخزنة، واستدعِ count(0, 0).

def findTargetSumWays(nums, target):
    n = len(nums)
    whole = sum(nums)
    # memo[i][total + whole]: ways for nums[i:] from this running total, -1 while unknown
    memo = [[-1] * (2 * whole + 1) for _ in range(n)]

    def count(i, total):
        if i == n:
            return 1 if total == target else 0
        if memo[i][total + whole] == -1:
            memo[i][total + whole] = count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
        return memo[i][total + whole]

    return count(0, 0)

احسب عدد المجموعات الجزئية التي يكون مجموعها (S + target) / 2

الفكرة

لتكن P مجموع الأعداد ذات الإشارة الموجبة، وN مجموع الباقي. عندئذٍ P - N = target وP + N = S، لذا 2P = S + target. يكون اختيار الإشارات صالحًا بالضبط عندما يكون مجموع مجموعة الأعداد ذات الإشارة الموجبة هو (S + target) / 2، وكل مجموعة جزئية كهذه تمثل اختيارًا واحدًا للإشارات.

تحسب ways[s] عدد المجموعات الجزئية للأعداد التي عولجت حتى الآن والتي يكون مجموعها s، بدءًا من ways[0] = 1. لكل عدد x، إما أن تتخطى المجموعة الجزئية التي يصل مجموعها إلى s العدد x، أو أن تضيفه إلى مجموعة جزئية يصل مجموعها إلى s - x. انتقل من أكبر قيمة لـs إلى أصغرها، كي تحتفظ ways[s - x] بقيمتها السابقة للعدد x، فلا يُستخدم أي عدد مرتين. يؤدي العدد 0 إلى إضافة كل مدخل إلى نفسه، فتتضاعف جميع الأعداد: وهذان هما خيارا الإشارة للصفر. يتطلب ذلك n × goal عملية جمع، بحد أقصى 2 × 10^4.

الخوارزمية

احسب S = sum(nums). إذا كان |target| > S أو كان S + target فرديًا، فأعد 0.
عيّن goal = (S + target) / 2، وأنشئ ways بطول goal + 1 مملوءة بالأصفار، ثم عيّن ways[0] = 1.
لكل x في nums، مرّ على s من goal نزولًا إلى x، وأضف ways[s - x] إلى ways[s].
أعِد ways[goal].

def findTargetSumWays(nums, target):
    whole = sum(nums)
    # plus - minus = target and plus + minus = whole, so plus = (whole + target) / 2
    if abs(target) > whole or (whole + target) % 2 == 1:
        return 0
    goal = (whole + target) // 2
    # ways[s]: how many subsets of the values seen so far add up to s
    ways = [0] * (goal + 1)
    ways[0] = 1
    for x in nums:
        # From the top down, so each value is used at most once
        for s in range(goal, x - 1, -1):
            ways[s] += ways[s - x]
    return ways[goal]

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

تخطّي فحص الزوجية. بالنسبة إلى [6, 3] والهدف 4، تُقرَّب (9 + 4) / 2 إلى الأسفل لتصبح 6، وتعطي المجموعة الجزئية {6} العدد 1 بدلًا من 0.
تخطّي فحص النطاق. بالنسبة إلى [1, 2, 3] والهدف -10، فإن (6 - 10) / 2 = -2، وهو حجم مصفوفة سالب.
ملء ways من الأسفل إلى الأعلى. عندئذٍ ينضم عدد إلى مجموعة جزئية تستخدمه بالفعل: [1, 3] مع الهدف 2 يعطي 2 بدلًا من 1.
اعتبار الصفر خيارًا واحدًا. تحتوي [0, 0, 0, 1, 0, 0] مع الهدف -1 على 32 إجابة، واحدة لكل نمط إشارة للأصفار الخمسة.
فهرسة ذاكرة مؤقتة باستخدام مجموع جارٍ سالب. أزِح كل مجموع بمقدار S، أو استخدم خريطة تجزئة.

أسئلة شائعة3

ما علاقة مسألة المجموع المستهدف بمسألة مجموع المجموعة الجزئية؟

يجب أن يكون مجموع الأعداد ذات الإشارة الموجبة مساويًا لـ (S + target) / 2، لذا فإن الإجابة هي عدد المجموعات الجزئية من nums التي يكون مجموعها كذلك. تحلّ أي خوارزمية برمجة ديناميكية لعدّ مجاميع المجموعات الجزئية هذه المسألة بعد إضافة شرطين: أن تكون القيمة عددًا صحيحًا، وألا تتجاوز |target| القيمة S.

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

تعمل برمجة عدّ المجموعات الجزئية الديناميكية في زمن O(n × S) وباستخدام ذاكرة O(S)، حيث إن S هو مجموع nums. ويستغرق الاستدعاء التعاودي مع التخزين المؤقت الزمن نفسه، لكنه يستخدم جدولًا بأبعاد n × (2S+1). وتجربة كل إشارة تستغرق O(2^n).

هل يمكن حل Target Sum باستخدام خريطة تجزئة للمجاميع التراكمية؟

نعم. اربط كل مجموع جارٍ يمكن الوصول إليه بعدد بادئات الإشارات التي تصل إليه، بدءًا من {0: 1}، وأنشئ الخريطة التالية من total + x وtotal - x لكل عدد. الإجابة هي العدد عند target. إنها عملية الاستدعاء التكراري مع التخزين المؤقت، لكن بتنفيذها من الأمام، وبالتعقيد الزمني نفسه O(n × S).

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

اختبار #1

اختبار #2

اختبار #3

الوسائط

nums = [2, 1, 1]
target = 2

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

Target Sum

الدالة

القيود

أمثلة

تلميحات

الحل

جرّب كلا الإشارتين لكل عدد

احفظ النتائج مؤقتًا حسب الموضع والمجموع الجاري

احسب عدد المجموعات الجزئية التي يكون مجموعها (S + target) / 2

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

أسئلة شائعة3

مسائل مشابهة