Subsets

+10

נתונה לך רשימה nums של מספרים שלמים שונים. החזר כל תת־קבוצה שלה, כולל הקבוצה הריקה והרשימה המלאה, כך ש־n ערכים נותנים 2^n תת־קבוצות. כתוב כל תת־קבוצה כשהערכים שלה בסדר עולה, ורשום את תת־הקבוצות בסדר לקסיקוגרפי: השווה בין שתי תת־קבוצות ערך אחר ערך, וההבדל הראשון הוא שקובע; תת־קבוצה שהיא תחילתה של תת־קבוצה אחרת מופיעה לפניה. עבור [1, 2] התשובה היא [[], [1], [1, 2], [2]].

פונקציה

subsets(nums: integer-array) → integer-2d-array

numsinteger-array: הערכים, כולם שונים, בכל סדר
מחזירהinteger-2d-array: כל תת־קבוצה, ממוינת בסדר עולה, ומופיעה בסדר לקסיקוגרפי

אילוצים

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10
כל הערכים ב־nums שונים.
nums יכולים להופיע בכל סדר.

דוגמאות

קלט: nums = [3, 1, 2]
פלט: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
הסבר: לאחר המיון, הערכים הם 1, 2, 3, ושלושה ערכים נותנים 2^3 = 8 תתי־קבוצות. [1, 2] מופיע לפני [1, 2, 3] כי הוא תחילית שלו, ו־[1, 2, 3] מופיע לפני [1, 3] כי 2 קטן מ־3 במיקום השני.

קלט: nums = [0]
פלט: [[], [0]]
הסבר: לערך אחד יש שתי תתי־קבוצות: לא לכלול אותו ולקבל [], או לקחת אותו ולקבל [0]. תת־הקבוצה הריקה תמיד מופיעה ראשונה.

קלט: nums = [5, -2]
פלט: [[], [-2], [-2, 5], [5]]
הסבר: הערכים ממוינים ל־-2 ול־5, לכן [-2, 5] נכתב בסדר הזה. כל תת־קבוצה שמכילה את ‎-2 מופיעה לפני [5], כי ‎-2 קטן מ־5.

+13 בדיקות נסתרות בשליחה

שאלת המשך

האם תוכל ליצור את אותה רשימה ללא רקורסיה, ולבנות כל תת־קבוצה ישירות מזו שקדמה לה?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

יש 2^n תת־קבוצות, ולכן שום שיטה לא מבצעת פחות מ־O(2^n) עבודה. השאלה האמיתית היא איך לייצר כל תת־קבוצה פעם אחת, בסדר הנדרש, בלי למיין אחר כך 1024 רשימות. חיפוש לאחור על פני הערכים הממוינים, תוך רישום כל צומת בעץ ההחלטה עם הכניסה אליו, עובר על תת־הקבוצות בדיוק בסדר לקסיקוגרפי.

מסכות סיביות, ואז מיון

האינטואיציה

סדר את הערכים הממוינים במיקומים 0 עד n-1. תת־קבוצה מסמנת כן או לא עבור כל מיקום, וזה מה שעושים n הביטים של מספר. לכן המספרים מ-0 עד 2^n-1 מייצגים את תת־הקבוצות: עבור [1, 2, 3], המסכה 5 היא 101 בבינארי, הביטים במיקומים 0 ו-2 דלוקים, והיא מייצגת את [1, 3]. מסכה 0 היא תת־הקבוצה הריקה ומסכה 7 היא הרשימה המלאה.

מסכות שונות מייצגות תת־קבוצות שונות, ולכל תת־קבוצה יש מסכה, ולכן הלולאה יוצרת את כל 2^n תת־הקבוצות בדיוק פעם אחת. קריאת הביטים ממיקום 0 ומעלה לאורך הערכים הממוינים כותבת כל תת־קבוצה בסדר עולה.

המסכות לא מתקבלות בסדר שהבעיה דורשת. מסכה 1 היא [1], מסכה 2 היא [2] ומסכה 3 היא [1, 2], ולכן [2] תופיע לפני [1, 2]. מתקנים זאת בעזרת מיון שמשווה ערכים בזה אחר זה ומציב קידומת לפני רצף ארוך ממנה. המיון עולה יותר מהיצירה: עבור 2^n תת־קבוצות נדרשות בערך n × 2^n השוואות, ובכל השוואה נקראים עד n ערכים. עבור n = 10 מדובר בכ-10^5 קריאות, מה שעדיין מהיר, אבל זו עבודה שהגישה הבאה כלל לא עושה.

אלגוריתם

מיין את nums כך שכל תת־קבוצה תיקרא בסדר עולה.
עבור כל מסכה מ־0 עד 2^n-1, אסוף את הערכים במיקומים שהביט שלהם מוגדר.
מיין את רשימת תת־הקבוצות: במיקום הראשון שבו שתיים מהן שונות, הערך הקטן יותר קודם, ואם אחת מהן מסתיימת קודם, היא באה ראשונה.
החזר את הרשימה הממוינת.

def subsets(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    for mask in range(1 << n):
        # Bit i of mask says whether values[i] is in this subset.
        result.append([values[i] for i in range(n) if (mask >> i) & 1])
    # Python compares lists position by position, and a prefix comes first.
    result.sort()
    return result

חיפוש עם חזרה לאחור: בחר, חקור, בטל את הבחירה

האינטואיציה

דמיינו את תתי-הקבוצות כעץ. השורש הוא תת-הקבוצה הריקה. מתחת לצומת אפשר להוסיף כל ערך שגדול מהערך האחרון שהוספתם. עבור הערכים הממוינים [1, 2, 3] לשורש יש את הילדים [1], [2] ו-[3]; ל-[1] יש את הילדים [1, 2] ו-[1, 3]; ל-[1, 2] יש את הילד [1, 2, 3]. כל תת-קבוצה מופיעה בעץ הזה בדיוק פעם אחת, כי יש רק דרך אחת לכתוב אותה בסדר עולה, וכל צומת הוא תשובה, לא רק העלים.

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

לכן הפלט הוא בסדר לקסיקוגרפי בלי למיין. מנסים את ילדי הצומת מהערך הקטן ביותר ועד הגדול ביותר, והמעבר מסיים ענף שלם לפני שהוא מתחיל בענף הבא. עבור [1, 2, 3] הוא מתעד את [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]: הסדר של מילון, שבו קידומת מופיעה לפני ההרחבות שלה.

בעץ יש 2^n צמתים, והעתקת נתיב עולה עד n, ולכן זמן הריצה הוא O(n × 2^n), כגודל התשובה עצמה. מלבד הפלט, שומרים נתיב אחד ומחסנית קריאות, שעומקם לכל היותר n.

אלגוריתם

ממיינים את הערכים.
כותבים explore(start). תחילה היא מוסיפה עותק של path לתוצאה.
לאחר מכן, עבור כל אינדקס i מ-start ועד הסוף: מוסיפים את values[i] ל-path (בוחרים), קוראים ל-explore(i+1) (חוקרים), ומסירים את הערך האחרון (מבטלים את הבחירה).
קוראים ל-explore(0) עם נתיב ריק ומחזירים את התוצאה.

def subsets(nums):
    values = sorted(nums)
    result = []
    path = []

    def explore(start):
        # Every node of the decision tree is a subset: record it on the way in.
        result.append(path[:])
        for i in range(start, len(values)):
            path.append(values[i])  # choose
            explore(i + 1)          # explore: only larger values may follow
            path.pop()              # un-choose

    explore(0)
    return result

מלכודות ומקרי קצה

רוב התשובות השגויות כאן נובעות מהסדר או משיתוף של רשימה אחת.

הוספה של path עצמו במקום עותק שלו. כל איבר מצביע אז לאותה רשימה, שהיא ריקה כשהמעבר מסתיים, ולכן מוחזרות 2^n עותקים של [].
שכחה למיין את nums. עם [3, 1, 2] העץ בונה את [3, 1], שאינו בסדר עולה, והמעבר כבר אינו בסדר לקסיקוגרפי.
תיעוד רק בעלים, כפי שהיית עושה עבור תמורות. כל צומת בעץ הזה הוא תת־קבוצה; תיעוד רק של מסלולים שמגיעים לסוף מחזיר מעט מדי תת־קבוצות.
רקורסיה על start+1 במקום על i+1. ערך יכול אז להופיע אחרי ערך גדול ממנו, או אפילו אחרי עצמו, ומתקבלות רשימות כמו [3, 2] ו-[3, 3] שאינן תת־קבוצות בסדר עולה.
שימוש בעץ הכללה או החרגה (הכרעה לגבי הערך 0, ואז הערך 1, וכן הלאה) ותיעוד העלים. הוא מוצא את כל 2^n תת־הקבוצות, אבל ניסיון לכלול קודם מציב את הרשימה המלאה ראשונה, וניסיון להחריג קודם מציב את [3] לפני [2]. אף אחד מהסדרים אינו לקסיקוגרפי.
משווה שממיין קודם לפי אורך מציג את [], [1], [2], [3], [1, 2], וזהו סדר שונה.

שאלות נפוצות4

כמה תת-קבוצות יש לקבוצה בעלת n איברים?

2^n. כל איבר נמצא בפנים או בחוץ, ללא תלות באחרים, ולכן מספר האפשרויות מוכפל: שתיים עבור האיבר הראשון, שתיים עבור השני, וכן הלאה. שלושה ערכים נותנים 8 תת־קבוצות ועשרה נותנים 1024, כולל תת־הקבוצה הריקה והקבוצה המלאה.

מהי סיבוכיות הזמן של בעיית תת־הקבוצות?

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

האם כדאי להשתמש בחיפוש עם חזרה לאחור או במסכות ביטים עבור תתי־קבוצות?

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

איך מטפלים בערכים כפולים בתתי־קבוצות?

מיין את הערכים, ואז בלולאה של פונקציית העזר לנסיגה לאחור דלג על ערך ששווה לערך שלפניו באותה רמה: i > start וגם values[i] == values[i-1]. העותק הראשון כבר בודק את כל תתי־הקבוצות שמשתמשות בו, ולכן ענף אחות שמתחיל בעותק השני רק יבנה מחדש את אותן תתי־קבוצות.

Python

def subsets(nums):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

nums = [3, 1, 2]

צפוי

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