Target Sum

Q: מה הקשר בין סכום יעד לבעיית סכום תת־קבוצה?

המספרים עם סימן פלוס חייבים להסתכם ב־ (S + target) / 2 , ולכן התשובה היא מספר תתי־הקבוצות של nums שסכומן זה. כל תכנות דינמי לספירת סכומי תתי־קבוצות יפתור זאת לאחר הוספת שתי בדיקות: הערך חייב להיות מספר שלם, ו־ |target| לא חייב להיות גדול מ־ S .

Q: מהי סיבוכיות הזמן של Target Sum?

תכנות דינמי לספירת תתי־קבוצות רץ בזמן 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, ולא בסימנים שהובילו ל־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, ושום מספר לא משמש פעמיים. אפס מוסיף כל ערך לעצמו, ובכך מכפיל את כל הספירות: אלה שני הסימנים האפשריים של אפס. מדובר ב־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 תשובות, אחת לכל תבנית סימנים של חמשת האפסים.
שימוש בסכום רץ שלילי כאינדקס במערך memo. יש להזיז כל סכום ב־S, או להשתמש במפת גיבוב.

שאלות נפוצות3

מה הקשר בין סכום יעד לבעיית סכום תת־קבוצה?

המספרים עם סימן פלוס חייבים להסתכם ב־(S + target) / 2, ולכן התשובה היא מספר תתי־הקבוצות של nums שסכומן זה. כל תכנות דינמי לספירת סכומי תתי־קבוצות יפתור זאת לאחר הוספת שתי בדיקות: הערך חייב להיות מספר שלם, ו־|target| לא חייב להיות גדול מ־S.

מהי סיבוכיות הזמן של Target Sum?

תכנות דינמי לספירת תתי־קבוצות רץ בזמן 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

בעיות דומות