Partition Equal Subset Sum

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

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

Q: מהי סיבוכיות הזמן של חלוקת מערך לתת־קבוצות שסכומן שווה?

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

Q: למה הלולאה הפנימית יורדת מהיעד אל הערך?

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

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

+10

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

פונקציה

canPartition(nums: integer-array) → boolean

numsinteger-array: הערכים החיוביים שיש לחלק לשתי קבוצות
מחזירהboolean: true כאשר הערכים יכולים להתחלק לשתי קבוצות שסכומיהן שווים, אחרת false

אילוצים

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 100

דוגמאות

קלט: nums = [6, 1, 4, 9, 2]
פלט: true
הסבר: הסכום הכולל הוא 22, ולכן כל קבוצה צריכה להגיע ל־11. הקבוצות 9 + 2 ו־6 + 1 + 4 מגיעות שתיהן ל־11, לכן התשובה היא true.

קלט: nums = [4, 7, 2, 9, 6]
פלט: false
הסבר: הסכום הכולל הוא 28, לכן כל קבוצה צריכה 14. הקבוצה שיש בה 9 צריכה עוד 5, ואף שילוב של 4, 7, 2 ו-6 לא נותן 5, לכן התשובה היא false אף על פי שהסכום הכולל זוגי.

קלט: nums = [1, 2, 3, 5]
פלט: false
הסבר: הסכום הכולל הוא 11. שני מספרים שלמים שווים תמיד מסתכמים במספר זוגי, לכן אי אפשר לחלק סכום אי-זוגי והתשובה היא false.

+18 בדיקות נסתרות בשליחה

שאלת המשך

כשאין חלוקה שווה, האם תוכל להחזיר את ההפרש הקטן ביותר האפשרי בין סכומי שתי הקבוצות?

רמזים

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

נפתחו 0 מתוך 3

פתרון

כל קבוצה חייבת להכיל בדיוק מחצית מהסכום הכולל, ולכן השאלה האמיתית היא האם תת־קבוצה כלשהי של nums מסתכמת ב־target = total / 2. בדיקת כל תת־הקבוצות עולה 2^n, וזה לא מעשי עבור 200 ערכים. עם זאת, הסכומים עצמם קטנים: target הוא לכל היותר 200 × 100 / 2 = 10^4. רישום הסכומים שאפשר להגיע אליהם, ערך אחד בכל פעם, הופך את החיפוש לטבלת תרמיל 0/1 שמתמלאת ב־O(n × sum) צעדים.

נסו כל תת־קבוצה באמצעות רקורסיה

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

האינטואיציה

התחל מהסכום הכולל. אם הוא אי-זוגי, אין חלוקה, כי סכום של שני מספרים שלמים שווים הוא תמיד זוגי. אחרת, הסכום של כל קבוצה חייב להיות בדיוק target = total / 2. ברגע שמוצאים ערכים שסכומם הוא target, הערכים שלא בחרת מסתכמים בעצמם למחצית השנייה. לכן מספיקה שאלה אחת: האם יש תת-קבוצה כלשהי שסכומה הוא target?

עבור על הערכים לפי הסדר ובחר אפשרות אחת לכל ערך: להכניס אותו לקבוצה הראשונה, או להשאיר אותו לקבוצה השנייה. פונקציית העזר reach(i, remaining) עונה אם הערכים מאינדקס i ואילך יכולים להסתכם ל-remaining. היא מחזירה true כשהערך remaining מגיע ל-0, false כשנגמרים הערכים או כשהוא יורד מתחת ל-0, ובכל מקרה אחר היא מנסה את שתי האפשרויות עבור nums[i].

כל תת-קבוצה היא מסלול אחד של בחירות, ולכן החיפוש לא יכול לפספס חלוקה, והתשובה נכונה. הוא איטי כי יש 2^n מסלולים, וקלט שאין בו חלוקה מאלץ אותו לנסות כמעט את כולם. קחו 199 עותקים של 100 ואחד של 98: הסכום הכולל הוא 19998, הערך 9999 לעולם לא מושג, והחיפוש מנסה כל דרך לבחור לכל היותר 99 מהמספרים 100, כלומר בערך 4 × 10^59 מסלולים. אפילו 40 ערכים נותנים 2^40, כלומר בערך 10^12 מסלולים.

אלגוריתם

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

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False

    # Can some of the values from index i on add up to exactly remaining?
    def reach(i, remaining):
        if remaining == 0:
            return True
        if i == len(nums) or remaining < 0:
            return False
        # Put nums[i] in the first group, or leave it for the second one
        return reach(i + 1, remaining - nums[i]) or reach(i + 1, remaining)

    return reach(0, total // 2)

מלאו טבלה לפי ערך וסכום

האינטואיציה

הרקורסיה שואלת שוב ושוב את אותה שאלה. reach(i, remaining) תלויה בשני מספרים בלבד: i מ־0 עד n ו־remaining מ־0 עד target. לכן יש לכל היותר (n+1) × (target+1) שאלות שונות, בערך 201 × 10001 ≈ 2 × 10^6 בגבולות, מעט מספיק כדי לענות על כל אחת מהן פעם אחת.

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

עבור [6, 1, 4, 9, 2] עם target 11, הסכומים שניתן להגיע אליהם מתרחבים מ־{0} ל־{0, 6}, ואז ל־{0, 1, 6, 7}, ואז ל־{0, 1, 4, 5, 6, 7, 10, 11}. הסכום 11 מופיע אחרי ה־4 (6 + 1 + 4), והשורות המאוחרות יותר משמרות אותו. התשובה היא can[n][target]. כל תא דורש זמן קבוע, ולכן גם הזמן וגם הזיכרון הם O(n × target).

אלגוריתם

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

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2
    n = len(nums)

    # can[i][s] is True when some of the first i values add up to s
    can = [[False] * (target + 1) for _ in range(n + 1)]
    can[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 and reach s - num with the values before it
            can[i][s] = can[i - 1][s] or (s >= num and can[i - 1][s - num])
    return can[n][target]

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

האינטואיציה

כל שורה בטבלה קוראת רק את השורה שמעליה, ולכן שורה אחת מספיקה אם מעדכנים אותה במקום: reach[s] מציין אם חלק מהערכים שנראו עד כה מסתכמים ל־s. הסכנה היא בסדר העדכונים. אם עוברים על s כלפי מעלה, ייתכן ש־reach[s-num] כבר הופעל על ידי אותו num. עם [3, 9] ויעד 6, הערך 3 מסמן את reach[3], ואז קורא אותו כדי לסמן את reach[6], כאילו היו לך שני ערכי 3, והתשובה שלך היא true עבור חלוקה שאינה קיימת.

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

אפשר גם לעצור ברגע ש־reach[target] הופך ל־true, כי ערכים מאוחרים יותר רק מוסיפים סכומים אפשריים ולעולם לא מסירים אותם. במקרה הגרוע ביותר עדיין נדרשים O(n × target) צעדים, בערך 2 × 10^6, והזיכרון מצטמצם ל־target + 1 ערכים בוליאניים.

אלגוריתם

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

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2

    # reach[s] is True when some of the values seen so far add up to s
    reach = [False] * (target + 1)
    reach[0] = True
    for num in nums:
        # Walk the sums downward so num is used at most once
        for s in range(target, num - 1, -1):
            if reach[s - num]:
                reach[s] = True
        if reach[target]:
            return True
    return reach[target]

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

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

מעבר על הסכומים כלפי מעלה בגרסה בת השורה האחת משתמש בערך יותר מפעם אחת. עם [3, 9] היעד הוא 6, ה־3 מסמן את הסכום 3 ואז את הסכום 6, ולכן התשובה היא true.
דילוג על בדיקת הזוגיות: עבור [1, 2] הסכום הכולל 3 מעוגל כלפי מטה ליעד 1, הערך 1 מגיע אליו, ולכן התשובה היא true עבור חלוקה שלא יכולה להתקיים.
מילוי חמדני, למשל מיון והוספה תמיד לקבוצה הקלה יותר, נכשל עם [3, 3, 2, 2, 2]: הוא מסתיים ב־7 לעומת 5, אף ש־3 + 3 = 2 + 2 + 2.
ערך שגדול מהיעד, כמו ב־[2, 2, 2, 10]. לולאה שיורדת מ־target ל־num תרוץ אז אפס פעמים, וזה נכון, אבל טווח כמו (num+1):(target+1) ב־R נספר לאחור ומשבש את הטבלה. דלגו על ערכים כאלה.
סכום זוגי אינו מספיק: הסכום של [4, 7, 2, 9, 6] הוא 28, ועדיין אין חלוקה.
ב־Lua וב־R מערכים מתחילים באינדקס 1, ולכן הרשומה של הסכום s נמצאת באינדקס s + 1.

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

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

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

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

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

למה הלולאה הפנימית יורדת מהיעד אל הערך?

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

האם ניתן לפתור את בעיית חלוקת המערך לתת־קבוצות בעלות סכום שווה באמצעות קבוצת סיביות?

כן. שמור את הסכומים שניתן להגיע אליהם בתור הביטים של מספר גדול אחד, כשהביט 0 בלבד מסומן בתחילה. עבור כל ערך, bits |= bits << num מוסיף את הערך הזה לכל סכום שניתן להגיע אליו בבת אחת, והתשובה היא האם הביט target מסומן. זו אותה טבלה, אבל כל מילת מכונה מטפלת ב־64 סכומים בבת אחת, ולכן בפועל היא פועלת הרבה יותר מהר.

Python

def canPartition(nums):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

nums = [6, 1, 4, 9, 2]

צפוי

true

Partition Equal Subset Sum

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

נסו כל תת־קבוצה באמצעות רקורסיה

מלאו טבלה לפי ערך וסכום

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

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

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

בעיות דומות