הבחנות:

1.    נניח שלקחנו אוסף כלשהו של תפוחים מבין התפוחים של סבתא סמית, ושניתן ליצור איתם את כל המשקלים מ-1 עד משקל W מסוים, ויש תפוח נוסף מחוץ לאוסף שלקחנו שמשקלו Y. ביחד אתו אפשר ליצור את כל המשקלים מ-1 עד W+Y.

2.    נניח שלקחנו אוסף כלשהו של תפוחים מבין התפוחים של סבתא סמית, ושהמשקל הכולל שלהם הוא W. אם כל שאר התפוחים שלא באוסף שבחרנו שוקלים יותר מ-W+1 (כלומר W+2 ומעלה), אי אפשר ליצור את המשקל W+1 על הצג.

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

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

נכונות: באינדוקציה מהבחנה 1, אם עד מקום מסוים ניתן להרכיב את כל המשקלים עד sum והתפוח הבא שוקל x, עכשיו סכום התפוחים sum+x ואפשר להרכיב את כל המשקלים עד אליו.

אלגוריתם:

-       מיין את המערך apple בסדר עולה

-       0 → sum

-       עבור כל i מ-1 עד n:

                  אם sum + 1 < apple[i]:

                           הדפס sum+1 וסיים

                  אחרת:

                           sum + apple[i] → sum

-       הדפס sum+1 וסיים // המקרה שבו ניתן להרכיב כל משקל  מ-1 עד סכום המשקלים

סיבוכיות זמן: המיון לוקח O(n log n), שאר הסריקה O(n), סה"כ O(n log n).