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.

سؤال إضافي

هل يمكنك إنشاء القائمة نفسها دون استخدام الاستدعاء الذاتي، مع بناء كل مجموعة جزئية مباشرةً من المجموعة التي تسبقها؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 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]، وهذا ترتيب مختلف.

أسئلة شائعة3

كم عدد المجموعات الجزئية لمجموعة تتكوّن من n عنصرًا؟

2^n. كل عنصر إما موجود أو غير موجود، بشكل مستقل عن العناصر الأخرى، لذا تتضاعف الخيارات: خياران للعنصر الأول، وخياران للعنصر الثاني، وهكذا. تعطي ثلاث قيم 8 مجموعات جزئية، وتعطي عشر قيم 1024، مع احتساب المجموعة الجزئية الخالية والمجموعة الكاملة.

ما هو التعقيد الزمني لمسألة المجموعات الجزئية؟

O(n × 2^n). يوجد 2^n مجموعة جزئية، وكتابتها تستغرق ما يصل إلى n خطوة، لذا فإن إرجاع الإجابة وحده يكلّف هذا القدر. يحقق التراجع هذا الحد، ولا يستخدم سوى O(n) مساحة إضافية. التوليد باستخدام أقنعة البتات سريع بالقدر نفسه، لكن ترتيب النتيجة بعد ذلك يضيف عاملًا آخر مقداره n.

هل أستخدم التراجع أو أقنعة البتات لإيجاد المجموعات الجزئية؟

أقنعة البتات قصيرة، ولا تحتاج إلى استدعاء ذاتي، وتجعل خيار الإدراج أو الاستبعاد ظاهرًا على هيئة بتات. وتُنتج خوارزمية التراجع المجموعات الجزئية بترتيب معجمي تلقائيًا، كما تتكيف مع الصيغ الشائعة: تخطي القيم المكررة، أو اختيار المجموعات الجزئية ذات الحجم k فقط، أو اختيار المجموعات الجزئية التي يصل مجموعها إلى قيمة مستهدفة، حيث يمكنك التوقف عن استكشاف فرع مبكرًا.

def subsets(nums):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

nums = [3, 1, 2]

الإخراج المتوقع

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