Combination Sum
נתונה לך רשימה candidates של מספרים שלמים חיוביים שונים ומספר שלם חיובי target. מצא את כל הצירופים של המועמדים שסכומם שווה בדיוק ל־target, כאשר אפשר להשתמש בכל מועמד כמה פעמים שרוצים. [2, 3, 3] ו־[3, 2, 3] הם אותו צירוף.
החזר כל צירוף בסדר עולה, ואת הצירופים בסדר לקסיקוגרפי: במיקום הראשון שבו שני צירופים שונים, הצירוף עם הערך הקטן יותר מופיע קודם.
פונקציה
- candidatesinteger-array
- הערכים השונים שבהם אפשר להשתמש, בכל סדר, וכל אחד מהם כמה פעמים שרוצים
- targetinteger
- הסכום של כל צירוף חייב להגיע בדיוק
- מחזירהinteger-2d-array
- כל צירוף שסכומו הוא היעד, כל אחד בסדר עולה, ברשימה לפי סדר לקסיקוגרפי
אילוצים
1 ≤ candidates.length ≤ 502 ≤ candidates[i] ≤ 5002 ≤ target ≤ 500- כל הערכים בתוך
candidatesשונים, ללא סדר מסוים. - לפחות צירוף אחד מגיע אל
target, ולכל היותר 150 צירופים עושים זאת.
דוגמאות
- קלט
- candidates = [6, 2, 3]target = 8
- פלט
- [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
- הסבר
- ארבעה 2ים, 2 + 3 + 3 ו־2 + 6 מסתכמים כולם ב־8, לפי הסדר של הערך השני שלהם. בלי 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, 3, 5]מופיע קודם כי הערך השני שלו, 3, קטן מ-4. שום שילוב של 4 ו-5 בלבד לא יוצר 11.
- קלט
- candidates = [4, 9]target = 9
- פלט
- [[9]]
- הסבר
- רק 9 בפני עצמו הוא התשובה: הכפולות של 4 נותנות 4, 8 ו־12, ו־4 + 9 כבר שווה ל־13.
שאלת המשך
כעת ניתן להשתמש בכל מועמד לכל היותר פעם אחת, ו־candidates יכול להכיל ערכים חוזרים. איך משנים את החיפוש כך שאף צירוף לא יופיע פעמיים?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
[2, 3, 3]ו-[3, 2, 3]הם אותו צירוף. אם תמיד תבנה צירוף כשהערכים שלו מסודרים בסדר עולה, בכמה דרכים אפשר לבנות כל אחד מהם?מיינו את המועמדים והגדילו צירוף ערך אחד בכל פעם. אחרי שמוסיפים את
nums[i], הערך הבא יכול להיות שובnums[i]או כל ערך מאוחר יותר, אך לעולם לא ערך מוקדם יותר.כתבו
backtrack(start, remaining). כאשרremainingהוא 0, שמרו עותק של הערכים הנוכחיים. אחרת, עברו בלולאה החל מ־start: הוסיפו ערך, קראו רקורסיבית עם אותו אינדקס ועם יתרה קטנה יותר, ואז הסירו את הערך. צאו מהלולאה בערך הראשון שגדול מ־remaining.
פתרון
המלכודת היא לבנות את אותו צירוף פעמיים: 2, 3, 3 ו־3, 2, 3 הם אותה תשובה. בנה כל צירוף בסדר עולה, כך שתהיה לו דרך אחת בלבד, ומיין את המועמדים כך שענף ייעצר ברגע שהערך הבא גדול ממה שנותר.
נסה כל מספר של כל מועמד
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
צירוף מתואר במלואו לפי מספר העותקים של כל מועמד שהוא כולל: [2, 3, 3] הוא 2 אחד, שני 3 ואין 6. נסו כל כמות עבור כל מועמד ממוין, מ־target / c ועד 0, ושמרו את הבחירות שסכומן בדיוק target. לכל צירוף יש רשימה אחת של כמויות, ולכן אף צירוף לא נמצא פעמיים. בחינת הכמויות הגדולות יותר קודם יוצרת סדר לקסיקוגרפי: במקום הראשון שבו שתי תשובות שונות, התשובה עם יותר עותקים של ערך עדיין מכילה את הערך הזה, בעוד האחרת מכילה ערך גדול יותר.
עבור [2, 3, 6] ויעד 8 יש 5 × 3 × 2 = 30 עלים עבור 3 תשובות. כל מועמד שגדול מ־target / 2 מכפיל את מספר העלים, כך ש־40 מועמדים כאלה פירושם 2^40, בערך 10^12.
אלגוריתם
- מיינו את המועמדים ושמרו ספירה אחת לכל ערך.
- בתוך
choose(i, total), נסו כל ספירהkמ-target / nums[i]ועד 0 וקראו ל-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] או כל ערך שמופיע אחריו, לעולם לא ערך מוקדם יותר. לצירוף יש סדר עולה יחיד, ולכן יש לו מסלול יחיד, ו-[3, 2, 3] לעולם לא נבנה.
עבור [2, 3, 6] ממוינים ויעד 8, המסלולים 2, 2, 2, 2 ו-2, 3, 3 ו-2, 6 מגיעים ל-8. המסלול 2, 2, 3 משאיר 1 ונעצר בלי לבדוק את 6, והמסלול 3, 3 משאיר 2, שאף ערך לא יכול להתאים אליו. זה 12 קריאות לעומת 30 העלים שבספירה.
בכל רמה הלולאה מנסה קודם ערכים קטנים יותר, ולכן התשובות מתקבלות בסדר לקסיקוגרפי. אף תשובה אינה תחילית של תשובה אחרת, מכיוון שהערכים חיוביים ושתיהן מגיעות לאותו סכום.
אלגוריתם
- מיינו את המועמדים.
- ב־
backtrack(start, remaining), שמרו עותק שלpathהמשותף כאשרremainingהוא 0. - אחרת, עברו בלולאה על
iהחל מ־start. אםnums[i] > remaining, צאו מהלולאה: כל הערכים שאחריו גדולים יותר. - הוסיפו את
nums[i], קראו ל־backtrack(i, remaining - nums[i]), ואז הסירו אותו. - קראו ל־
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.
שאלות נפוצות3
מהי סיבוכיות הזמן של Combination Sum?
חיפוש הנסיגה הוא אקספוננציאלי. עם n מועמדים, יעד t והמועמד הקטן ביותר m, צירוף מכיל לכל היותר t/m ערכים, עם לכל היותר n אפשרויות לכל אחד: O(n^(t/m)). המקום הנוסף הוא O(t/m) עבור הנתיב ומחסנית הקריאות, בנוסף לפלט.
למה מבצעים קריאה רקורסיבית עם i ולא עם i + 1 ב-Combination Sum?
רקורסיה עם i מאפשרת לערך הבא להיות שוב אותו מועמד, וכך אפשר להשתמש בערך יותר מפעם אחת. רקורסיה עם i + 1 מתקדמת מעבר אליו, כך שאפשר להשתמש בכל מועמד לכל היותר פעם אחת.
האם אפשר לפתור את בעיית סכום הצירופים באמצעות תכנות דינמי?
כן. עבור כל סכום מ־0 עד target, שומרים את הצירופים שמגיעים אליו, ומוסיפים מועמד אחד בכל פעם כדי שכל רשימה תישאר בסדר עולה. היא לעולם לא בוחנת שוב מבוי סתום, אבל שומרת כל צירוף חלקי עבור כל סכום, מה שדורש הרבה יותר זיכרון. מכיוון שהפלט עצמו יכול להיות אקספוננציאלי, בדרך כלל משתמשים בחיפוש עם חזרה לאחור.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def combinationSum(candidates, target):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
candidates = [6, 2, 3] target = 8
הפלט הצפוי
[[2, 2, 2, 2], [2, 3, 3], [2, 6]]