לא פסבדו קוד...
התשובה לשני השאלות היא אחת. אם תוכל להוכיח שקיימת תת-קבוצה כזו תוכל לענות גם על שאלה 2. אני לא אתן לך פתרון מפורט. אבל אולי זה יעזור לך אם אני יאמר לך שהבעיה הזו עתיקת יומין ויש לה אפילו שם מכובד: "Subset Sum Problem" או בשמה הקריפטוגראפי Knapsack, בעיה זו נחשבת NP-complete ויש לה כמה פתרונות ידועים אחד נאיבי ב-O(2^n) ואחד טוב יותר שנקרא: meet in the middle שרץ ב-O(n2^(n\2)). (יש עוד אחד שאתה אפילו לא רוצה לשמוע את השם שלו שייך לתחום הקריפטוגרפיה ומסובך לאלה). האלגוריתם meet-in-the-middle (הטוב ביותר לבעיה הכללית), משתמש בטבלה ממויינת ומבצע חיפוש בינארי, עם וקטורים (בוליאני) באורך n. טוב כל זה היה רק בכללות. רציתי להשאיר לך קצת עבודה... טיפ קטן, קל למצוא באינטרנט חומר על זה. ועוד טיפ קטן, כדאי שתנסה בכוחות עצמך לפני שאתה מעתיק פסבדו קוד ממישהו אחר. בהצלחה.
