Combination Sum

Q: למה מבצעים קריאה רקורסיבית עם i ולא עם i + 1 ב־Combination Sum?

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

בינוניחיפוש לאחור

+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 שווה 8, וכך גם 2 + 3 + 3 ו־2 + 6. שלושתם מתחילים ב־2, ולכן הערך השני קובע את הסדר: 2, אחר כך 3, ואז 6. בלי 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 קטן מה־4, לכן [3, 3, 5] מופיע ראשון. שום שילוב של 4 ו־5 בלבד לא שווה ל־11.

קלט: candidates = [4, 9]target = 9
פלט: [[9]]
הסבר: 9 לבדו הוא צירוף. 4 נותן רק את 4, 8 ו־12 בדרך מעבר ל־9, ו־4 + 9 הוא כבר 13, לכן [9] הוא התשובה היחידה.

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

שאלת המשך

כעת אפשר להשתמש בכל מועמד לכל היותר פעם אחת, ו-candidates יכול להכיל ערכים חוזרים. איך משנים את החיפוש כך שאף שילוב לא יופיע פעמיים?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

נסו כל ספירה של כל מועמד

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

האינטואיציה

שילוב מתואר במלואו לפי מספר העותקים של כל מועמד שבהם הוא משתמש. עבור [6, 2, 3] ויעד 8, התשובה [2, 3, 3] היא 2 אחד, שני 3-ים וללא 6. לכן, דרך אחת למצוא כל תשובה היא לנסות כל מספר אפשרי של עותקים עבור כל מועמד ולשמור את האפשרויות שסכומן הכולל הוא בדיוק target. אפשר להשתמש במועמד c לכל היותר target / c פעמים, ולכן מספר העותקים שלו נע בין 0 לגבול הזה.

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

הבעיה היא גודל העץ. מספר העלים הוא המכפלה של target / c + 1 עבור כל המועמדים: עבור [2, 3, 6] הממוינת ויעד 8, זה 5 × 3 × 2 = 30 עלים עבור 3 תשובות. כל מועמד שגדול מ-target / 2 מכפיל את מספר העלים, אף שאפשר להשתמש בו לכל היותר פעם אחת, ולכן 40 מועמדים כאלה לבדם פירושם 2^40, כ-10^12 עלים. הבדיקות הגדולות בנויות כך, והגישה הזאת לא יכולה להשלים אותן.

אלגוריתם

ממיינים את המועמדים ויוצרים מערך של ספירות, אחת לכל ערך.
כותבים את choose(i, total), שקובעת את הספירה של הערך באינדקס i.
עבור k, מ־target / nums[i] ועד 0, קובעים את הספירה ל־k וקוראים ל־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], כי אפשר לחזור על מועמד, או כל ערך מאוחר יותר, אבל לעולם לא ערך מוקדם יותר. לכן הקריאה שהוסיפה את האינדקס i מבצעת לולאה רק מ-i והלאה. לכל צירוף יש סדר עולה יחיד, ולכן יש לו מסלול יחיד בעץ, וצירוף כפול כגון [3, 2, 3] לעולם לא נבנה.

הנה העץ כולו עבור [2, 3, 6] ממוין ויעד 8. בשורש נשארים 8, ונוסו הערכים 2, 3 ו-6. מתחת ל-2 נשארים 6. מתחת ל-2, 2 נשארים 4, ואחרי 2, 2, 2 נשארים 2, שאותם עוד 2 הופך לתשובה [2, 2, 2, 2]; אחרי 2, 2, 3 נשאר 1 והמסלול מסתיים. מתחת ל-2, 3 נשארים 3, ואפשר לנסות רק 3 ו-6, והערך 3 נותן את [2, 3, 3]. מתחת ל-2, 6 לא נשאר כלום: [2, 6]. מתחת ל-3 אפשר לנסות רק 3 ו-6, ואחרי 3, 3 נשארים 2, שאף אחד מהם אינו משלים. מתחת ל-6 נשארים 2, ואפשר לנסות רק 6. 12 קריאות בסך הכול, לעומת 30 העלים של הגישה הראשונה.

מיון הופך מבוי סתום לעצירה מוקדמת. כש-nums[i] גדול ממה שנשאר, כל ערך מאוחר יותר גדול גם הוא, ולכן יוצאים מהלולאה בעזרת break במקום לבדוק את השאר. בעץ שלמעלה, הצומת 2, 2, 3, שבו נשאר 1, בודק את 3, רואה שהוא לא מתאים, ולא בודק כלל את 6. החיפוש מבקר רק בקידומות שהסכום שלהן עדיין לכל היותר target, ולכן הבדיקות הגדולות שמכשילות את הגישה הראשונה דורשות כאן רק כמה אלפי קריאות.

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

אלגוריתם

ממיינים את המועמדים בסדר עולה.
כותבים את backtrack(start, remaining), שמשתפת רשימה אחת path. אם remaining הוא 0, שומרים עותק של path.
אחרת, עוברים בלולאה על i מ-start עד הסוף. אם nums[i] > remaining, יוצאים מהלולאה: כל הערכים הבאים גדולים יותר.
מוסיפים את nums[i], קוראים ל-backtrack(i, remaining-nums[i]) עם i, ולא עם i + 1, כדי שהערך יוכל לחזור על עצמו, ואז מסירים אותו.
קוראים ל-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.
החזרת הצירופים בסדר שמכתיבה הקלט הלא ממוין. הרשימה הצפויה מסודרת בסדר לקסיקוגרפי, והחיפוש הממוין מפיק אותה כך ללא מיון נוסף.
ב-Lua וב-R, מערכים מתחילים ב-1, לכן הקריאה הראשונה מתחילה באינדקס 1 והלולאה רצה עד לאורך המערך.

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

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

החיפוש באמצעות חזרה לאחור הוא מעריכי. עם n מועמדים, יעד t והמועמד הקטן ביותר m, שילוב מכיל לכל היותר t/m ערכים, ובכל צעד יש לכל היותר n אפשרויות, ולכן העבודה חסומה על ידי O(n^(t/m)). הגיזום של מועמדים ממוינים משאיר את מספר הקריאות בפועל נמוך בהרבה, כי החיפוש מבקר רק בקידומות שסכומן עדיין לכל היותר t. המרחב הנוסף הוא O(t/m) עבור הנתיב הנוכחי ומחסנית הקריאות, בנוסף לפלט.

למה מבצעים קריאה רקורסיבית עם i ולא עם i + 1 ב־Combination Sum?

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

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

צרו כל צירוף לפי סדר קבוע, בסדר עולה. אינדקס ההתחלה כופה זאת: לאחר הוספת nums[i], החיפוש בודק רק את nums[i] ואת הערכים שאחריו. כך לכל צירוף יש מסלול יחיד בדיוק בעץ החיפוש, ולכן הוא נוצר פעם אחת, ואין צורך בקבוצה או בהסרת כפילויות בסוף.

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

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

Python

def combinationSum(candidates, target):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

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

צפוי

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