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

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

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

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

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

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

אפילו אם נלך על השיטה האיטית של בדיקת כל האפשרויות, ידיעת הסכום הכולל יכולה לעזור לנו מאוד באופטימיזציה בשטח. אם אני מקבל את המערך A ומגלה שהסכום שלו הוא X, אז בעצם אני מחפש חלוקה לשני מערכים, a₁ ו-a₂, שהסכום של כל אחד מהם הוא בהכרח X/2. זה אומר שצריך לסכוֹם בכל סיבוב רק תת-מערך אחד, לא את שניהם, והנה קיצרנו חלק מזמן הבדיקה פי שניים.

לאור התובנה הזו, המשימה שלנו גולשת כעת לכיוון אחר. במקום לחלק לשני מערכים ואז לסכוֹם אחד מהם, אנחנו יכולים להסתכל על המערך השלם וישר לחפש בו קבוצת איברים שסכומם X/2. אם נמצא קבוצה כזו, אז בהכרח האיברים שנשארו "בחוץ" יהוו את הקבוצה השנייה.

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

בכל מקרה, החיפוש של קבוצת איברים שסכומם X/2 חייב להתבצע באופן רקורסיבי (או שווה-ערך לרקורסיה). אשמח לגלות שאני טועה אבל נדמה לי שאין דרך אחרת*. הרקורסיה תעצור כשנגמרו האפשרויות או כשהסכום הגיע ל-X/2, ולכאורה אפשר גם לצמצם קצת את עץ החיפוש אם שמים לב לקבוצות של ערכים זהים. הנקודה האחרונה שצריך לקחת בחשבון, אם אנחנו מדברים על מספרים עשרוניים, היא הייצוג הלא-מושלם שלהם במחשב. סטייה של 0.00000000001, שמקורה במגבלות של טיפוס float ולא במספרים המקוריים שבמערך, יכולה לשבש את הזיהוי של הפתרון הנכון. אולי זו זהירות-יתר, בכל אופן בראיון עבודה הייתי שואל את המראיינים לגבי זה.

*אחרי שכתבתי את השורה הזו, נזכרתי בבעיה מפורסמת במדעי המחשב עם קווי דמיון מסוימים – knapsack problem. היא מורכבת יותר מהחידה שלנו, אבל שיטוט קצר בוויקיפדיה העלה גרסה פשוטה, subset sum problem, שלה-עצמה יש גרסה עוד יותר פשוטה בשם partition problem, שהיא בדיוק מה שאנחנו מנסים לפתור כאן. רק מה, בגרסה בוויקיפדיה כן כתוב במפורש שמדובר על מספרים שלמים!

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

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