Subset Sum Problem

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

חלוקת סכום שווה לתת־קבוצה היא בעיית סכום תת־קבוצה עם target = total / 2 , לאחר בדיקה שהסכום הכולל זוגי. סכום תת־קבוצה היא בעיית תרמיל 0/1 שבה כל ערך הוא המשקל של עצמו, ויש למלא את התרמיל בדיוק, ולכן הטבלה מכילה ערכים בוליאניים במקום ערכים מיטביים.

Q: איך מוצאים אילו ערכים מגיעים ליעד?

שמור את הטבלה המלאה והתחל ב־ made[n][target] . התקדם שורה אחת בכל פעם: אם made[i-1][s] הוא true, אז nums[i-1] לא היה נחוץ; אחרת, רשום אותו והפחת אותו מ־ s . עצור כשהסכום מגיע ל־0 ויש לך בחירה תקינה אחת.

בינוניתכנון דינמי

+10

nums מכיל מספרים שלמים חיוביים, ו-target הוא מספר שלם חיובי. האם תוכל לבחור חלק מהערכים, כל מיקום לכל היותר פעם אחת, כך שסכומם יהיה בדיוק target? החזר true אם הדבר אפשרי, ו-false אם אין בחירה מתאימה.

פונקציה

isSubsetSum(nums: integer-array, target: integer) → boolean

numsinteger-array: הערכים החיוביים שאפשר לבחור מתוכם
targetinteger: הסכום המדויק שעל הערכים שנבחרו להגיע אליו
מחזירהboolean: true כאשר חלק מהערכים מסתכמים בדיוק ל־target, אחרת false

אילוצים

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 10⁴
1 ≤ target ≤ 10⁴

דוגמאות

קלט: nums = [8, 3, 11, 5, 7]target = 15
פלט: true
הסבר: 8 + 7 = 15, לכן התשובה היא true. הבחירה 3 + 5 + 7 עובדת גם היא; בחירה אחת מספיקה.

קלט: nums = [6, 9, 12, 15]target = 20
פלט: false
הסבר: כל ערך הוא כפולה של 3, ולכן גם כל סכום שלהם הוא כפולה של 3. 20 אינו כפולה של 3, ולכן התשובה היא false.

קלט: nums = [4, 1, 2]target = 8
פלט: false
הסבר: כל שלושת הערכים יחד מסתכמים ב־4 + 1 + 2 = 7, שזה פחות מ־8, ולכן אף בחירה לא יכולה להגיע אליו והתשובה היא false.

שאלת המשך

שני ערכים שווים במיקומים שונים נחשבים לבחירות שונות. כמה בחירות מגיעות ל־target?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

בחירה היא כן או לא עבור כל ערך, ולכן 200 ערכים נותנים 2^200 אפשרויות בחירה. עם זאת, חשובות רק סכומים עד target ≤ 10^4. תעדו אילו סכומים אפשר ליצור מהערכים עד כה: כל ערך חדש מזיז את התיעוד הזה בגודל שלו, והחיפוש הופך לטבלה של n × target ערכים בוליאניים.

קחו או דלגו על כל ערך

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

canMake(i, remaining) בודקת אם הערכים ממיקום i ואילך יכולים להסתכם בדיוק ל־remaining. בוחרים את nums[i] אם הוא מתאים, וכך נשארים remaining-nums[i] עבור השאר; אם זה נכשל, מדלגים עליו. כל בחירה היא מסלול אחד, ולכן החיפוש מוצא בחירה בכל פעם שקיימת כזו.

כשלא קיימת בחירה כזו, הוא עובר על כולם. כשיש 200 כפולות של 3, שכל אחת מהן לכל היותר 300, ויעד של 9998, שום בחירה לא מצליחה, ובכל זאת כל 33 ערכים נשארים מתחת ליעד: יותר מ־10^37 מסלולים.

אלגוריתם

כתבו canMake(i, remaining).
ערך remaining של 0 פירושו שהבחירה הושלמה: החזירו true. אם לא נותרו ערכים ועדיין יש משהו שצריך ליצור, החזירו false.
אם nums[i] ≤ remaining ו-canMake(i+1, remaining-nums[i]) הוא true, החזירו true.
אחרת, החזירו canMake(i+1, remaining).
החזירו canMake(0, target).

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

    # Can some of nums[i], nums[i+1], ... add up to exactly remaining?
    def can_make(i, remaining):
        if remaining == 0:
            return True
        if i == n:
            return False
        if nums[i] <= remaining and can_make(i + 1, remaining - nums[i]):
            return True  # take nums[i]
        return can_make(i + 1, remaining)  # skip it

    return can_make(0, target)

מלאו טבלה של סכומים שניתן להגיע אליהם

האינטואיציה

הרקורסיה תלויה רק במיקום ובסכום שנותר בין 0 ל־target, ומסלולים רבים מגיעים לאותו זוג. במקום זאת, מלא טבלה. made[i][s] הוא true כאשר בחירה מתוך i הערכים הראשונים מסתכמת בדיוק ב־s; הבחירה הריקה נותנת 0. עם num = nums[i-1], הסכום s מתקבל אם הוא התקבל בלי num, כלומר made[i-1][s], או אם num משלים את s-num, כלומר made[i-1][s-num], כאשר s ≥ num.

בדוגמה הראשונה, אחרי 8 הסכומים שהתקבלו הם 0 ו־8. ה־3 מוסיף את 3 ואת 11, ה־11 מוסיף רק את 14, ה־5 מוסיף את 5 ואת 13, ו־8 + 7 מגיע ל־15. בגבולות הנתונים, הטבלה מכילה 201 × 10001 תאים, כלומר בערך 2 × 10^6 צעדים.

אלגוריתם

הקצה ל־made n+1 שורות ו־target+1 ערכים בוליאניים, כולם false. סמן את made[0][0] כ־true עבור בחירה ריקה.
שורה i מטפלת בערך num = nums[i-1], עבור i = 1 עד n.
עבור כל סכום s מ־0 עד target, הגדר את made[i][s] לערך של made[i-1][s].
אם s ≥ num וגם made[i-1][s-num] הוא true, הגדר את made[i][s] ל־true.
החזר את made[n][target].

def isSubsetSum(nums, target):
    n = len(nums)
    # made[i][s]: some of the first i values add up to exactly s
    made = [[False] * (target + 1) for _ in range(n + 1)]
    made[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 on top of a sum of s-num
            made[i][s] = made[i - 1][s] or (s >= num and made[i - 1][s - num])
    return made[n][target]

שורת סכומים אחת, מתעדכנת מלמעלה

האינטואיציה

כל שורה קוראת רק את השורה שלפניה, ולכן מערך אחד made[s] יכול להכיל את הנתונים. אם כותבים עליו מחדש כלפי מעלה, ערך מזין את עצמו: עם nums = [5] ויעד 10, s = 5 הופך לאמת, ואז s = 10 קורא את הערך החדש הזה, ומשתמש ב־5 פעמיים.

התקדמו מ־target כלפי מטה עד num. הקריאה ב־s-num מגיעה לתא נמוך יותר שהמעבר עדיין לא כתב אליו מחדש, ולכן היא רואה את השורה מלפני num. אם סכום ניתן להרכבה, הוא נשאר ניתן להרכבה, ולכן אפשר לעצור ברגע ש־made[target] הוא true. צריכת הזיכרון יורדת ל־target + 1 ערכים בוליאניים.

אלגוריתם

התחל במערך יחיד של ערכים בוליאניים באורך target + 1, שבו רק made[0] הוא true.
קח את הערכים לפי הסדר. עבור כל num, הרץ את s כלפי מטה מ־target עד num.
בכל מקום שבו made[s-num] מכיל true, סמן את made[s].
עצור והחזר true ברגע ש־made[target] מסומן.
אם כל הערכים נוצלו קודם לכן, התשובה היא false.

def isSubsetSum(nums, target):
    # made[s]: some of the values seen so far add up to exactly s
    made = [False] * (target + 1)
    made[0] = True
    for num in nums:
        # Downward, so made[s - num] still ignores num
        for s in range(target, num - 1, -1):
            if made[s - num]:
                made[s] = True
        if made[target]:
            return True
    return False

מלכודות ומקרי קצה

לולאה עולה על הסכומים משתמשת בערך פעמיים: [3] עם יעד 9 מחזיר true.
שוכחים את made[0] = true. כל סכום נבנה על הבחירה הריקה, ולכן כל התשובות יוצאות false.
בוחרים קודם את הערכים הגדולים ביותר. עם [6, 5, 5] ויעד 10, בחירה ב־6 משאירה 4, שאי אפשר ליצור, בעוד ש־5 + 5 = 10.
ערך שגדול מ־target, כמו ב־[10000] עם יעד 1, לא אמור לשנות דבר. num...target של Swift עוצר את התוכנית, ו־(num+1):(target+1) של R סופר לאחור, לכן קודם בדקו num ≤ target.
ב־Lua וב־R, הערך עבור הסכום s נמצא באינדקס s + 1.

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

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

הטבלה דורשת זמן O(n × target), בערך 2 × 10^6 צעדים עבור 200 ערכים ויעד של 10^4, ושורה אחת מצמצמת את הזיכרון ל־O(target). העלות תלויה בגודל המספרי של היעד, ולכן השיטה היא פסאודו־פולינומית וחסרת תועלת עבור יעד כמו 10^18. באופן כללי, בעיית סכום תת־הקבוצה היא NP-complete.

מה הקשר בין בעיית סכום תת־קבוצה לבעיות חלוקה לתת־קבוצות שוות וסכמת תרמיל 0/1?

חלוקת סכום שווה לתת־קבוצה היא בעיית סכום תת־קבוצה עם target = total / 2, לאחר בדיקה שהסכום הכולל זוגי. סכום תת־קבוצה היא בעיית תרמיל 0/1 שבה כל ערך הוא המשקל של עצמו, ויש למלא את התרמיל בדיוק, ולכן הטבלה מכילה ערכים בוליאניים במקום ערכים מיטביים.

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

הרעיון עובד, הקוד שלמעלה לא. כשיש מספרים שליליים, הסכומים שאפשר להגיע אליהם נעים מסכום המספרים השליליים ועד סכום המספרים החיוביים, לכן יש להזיז כל אינדקס לפי הסכום הנמוך ביותר ולמלא את השורה באותה דרך. אי אפשר עוד לדלג על ערך שגדול מהסכום שנותר.

איך מוצאים אילו ערכים מגיעים ליעד?

שמור את הטבלה המלאה והתחל ב־made[n][target]. התקדם שורה אחת בכל פעם: אם made[i-1][s] הוא true, אז nums[i-1] לא היה נחוץ; אחרת, רשום אותו והפחת אותו מ־s. עצור כשהסכום מגיע ל־0 ויש לך בחירה תקינה אחת.

def isSubsetSum(nums, target):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

nums = [8, 3, 11, 5, 7]
target = 15

הפלט הצפוי

true

Subset Sum Problem

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

קחו או דלגו על כל ערך

מלאו טבלה של סכומים שניתן להגיע אליהם

שורת סכומים אחת, מתעדכנת מלמעלה

מלכודות ומקרי קצה

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

בעיות דומות