אתגר תכנותי: סכום השילובים combination sum

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

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

הצגת הבעיה

הבעיה:
נתון מערך של מספרים שלמים candidates ומספר שלם target. יש להחזיר רשימה של כל השילובים הייחודיים של המספרים מתוך candidates אשר מסתכמים ל- target. אותו מספר יכול להיבחר מספר פעמים ללא הגבלה.

• שני שילובים נחשבים לייחודיים אם תדירות הבחירה של לפחות אחד מהמספרים שונה.

נראה דוגמה:

קלט:

candidates = [1, 5, 3, 2]
target = 4

פלט:

[1, 1, 1, 1]
[1, 1, 2]
[1, 3]
[2, 2]

נסביר:

בדוגמה זו, עבור הקלט [1, 5, 3, 2] הקומבינציות הייחודיות המסתכמות ב-4 הם:

[1, 1, 1, 1]
[1, 1, 2]
[1, 3]
[2, 2]

סקירת האלגוריתם

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

• חיפוש רקורסיבי: מנסים להוסיף בצורה רקורסיבית כל מספר לקומבינציה (=שילוב).
• בחירה בלתי מוגבלת: מאחר וכל מספר יכול להיבחר מספר פעמים, ממשיכים לחקור את אותו מספר ולא עוברים מיד למספר הבא.
• במידה ועוברים את סכום המטרה לא ממשיכים לחקור, וחוזרים אחורה backtrack כדי להמשיך לחקור הלאה.

הדיאגרמה הבאה תמחיש זאת:

                      []
                    /  |  
                   1   5   3...
                  /    |    
             [1,1]     X    [3,1]
              /    
         [1,1,1] [1,1,2] ...
           /  
    [1,1,1,1]   

• כל ענף מייצג החלטה לכלול מספר מסוים, והאלגוריתם חוזר אחורה (backtracks) במידה שהסכום עובר את היעד.

יישום

להלן מימוש הפתרון בפייתון:

def combination_sum(coins, target):
   len_coins = len(coins)
   uniq_combinations = []


   def backtrack(start_idx=0, current_combination=[], current_sum=0):
       # Base case: when the current sum equals target
       if current_sum == target:
           uniq_combinations.append(list(current_combination))
           return
      
       # Recursive case: loop the items starting at `start_idx`
       for coin_idx in range(start_idx, len_coins):
           if current_sum + coins[coin_idx] <= target:
               # Add the current item to the current combination
               current_combination.append(coins[coin_idx])
               # Continue exploring
               backtrack(coin_idx, current_combination, current_sum + coins[coin_idx])
               # Backtrack: to search for another possibility
               current_combination.pop()
  
   # Start the process from index=0
   backtrack()


   return uniq_combinations

ננסה את הפונקציה:

print(combination_sum([1, 5, 3, 2], 4))

נסביר:

1. אתחול:
• נגדיר פונקציית עזר backtrack שמקבלת אינדקס התחלה, השילוב הנוכחי והסכום הנוכחי.
• נאתחל רשימה ריקה uniq_combinations שתאחסן את כל השילובים התקפים.
2. מקרה בסיס:
• כאשר current_sum שווה ל- target, מוסיפים עותק של השילוב הנוכחי לרשימת הפתרונות.
3. מקרה רקורסיבי:
• לולאה רצה על מערך המספרים החל מהאינדקס start_idx.
• עבור כל מספר, בודקים אם הוספתו לסכום הנוכחי אינה עוברת את ה- target.
• אם לא עוברת, מוסיפים את המספר לשילוב הנוכחי וקוראים לפונקציה backtrack עם הסכום המעודכן.
• לאחר הקריאה הרקורסיבית, מסירים את המספר מהשילוב (backtracking) ועוברים לבדוק אפשרויות נוספות.

טיפול במקרי קיצון:

• מערך ריק: אם מערך המספרים ריק, הפונקציה תחזיר רשימה ריקה.
• אין פתרון תקף: אם אין שום שילוב שמסתכם ל- target, האלגוריתם יחזיר רשימה ריקה.

הערכת ביצועי האלגוריתם

זמן ריצה:

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

סיבוכיות מקום:

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

יישומים בעולם האמיתי

תוכל ליישם את הרעיונות שלמדת בפתרון בעיית סכום השילובים לצורך התמודדות עם אתגרים בעולם האמיתי, לדוגמה:

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

נסכם

במדריך זה חקרנו את בעיית סכום השילובים והסברנו את גישת ה-backtracking שלב אחר שלב. בכלל כך:

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

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

זהו, מקווה שהמדריך היה מובן ושימושי! שתהיה לך עבודה מוצלחת עם הקוד והאתגרים הבאים.

למידע נוסף והעמקה, מומלץ לעיין במדריכים האחרים בסדרה

מבוא לbacktracking או מציאת כל השילובים באמצעות אלגוריתם גישוש נסוג

שימוש באלגוריתם backtracking גישוש נסוג לפתרון האתגר של N מלכות

קוד לפתרון סודוקו בעזרת אלגוריתם backtracking גישוש נסוג

רקורסיה בפייתון - כל מה שרצית לדעת ועוד כמה דברים חשובים

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים