مجموعة فرعية Leetcode


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون أجهزة آبل بلومبرغ ByteDance Facebook جوجل Microsoft أوراكل
مجموعة التراجع قطعة معالجة البت بت

في مشكلة المجموعة الفرعية ، قدمنا ​​مجموعة من الأعداد الصحيحة المتميزة ، والأرقام ، وطباعة جميع المجموعات الفرعية (مجموعة الطاقة).

ملاحظة: يجب ألا تحتوي مجموعة الحلول على مجموعات فرعية مكررة.

المصفوفة A هي مجموعة فرعية من المصفوفة B إذا كان من الممكن الحصول على a من B عن طريق حذف بعض العناصر (ربما صفر أو جميعها).

مثال

الإدخال:

[1 و 2 و 3]

الإخراج:

[1] ، [2] ، [1 ، 2] ، [3] ، [1 ، 3] ، [2 ، 3] ، [1 ، 2 ، 3]

الأسلوب 1: الحل التكراري باستخدام معالجة البتات

يمكن تمثيل كل مجموعة فرعية من مجموعة من العناصر n كسلسلة من n بتات ، والتي تتوافق مع عدد صحيح بين 0 ... 2n-1. تشير العناصر الموجودة في تسلسل البتات إلى العناصر المضمنة في المجموعة الفرعية.

خوارزمية

  1. نعلن مجموعة من المتجهات "الجواب" التي سنخزن فيها جميع مجموعاتنا الفرعية.
  2. قم بتهيئة متغير n يمثل حجم nums_array.
  3. قم بتشغيل حلقة لـ I في النطاق من 0 إلى 2n-1
    1. قم بتهيئة مصفوفة "temp" حيث سنخزن مجموعتنا الفرعية الحالية.
    2. قم بتشغيل حلقة لـ j في النطاق من 0 إلى n-1
      1. إذا تم تعيين الجزء jth من I ، فقم بإضافة الأعداد [i] إلى الصفيف المؤقت.
    3. أضف مصفوفة "temp" إلى "ans"
  4. طباعة مجموعة الجواب النهائية.

تنفيذ طباعة جميع المجموعات الفرعية

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> ans;
    for (int i = 0; i < (1 << (nums.size())); i++)
    {
        vector<int> temp;
        for (int j = 0; j < nums.size(); j++)
        {
            if (i & (1 << j))
            {
                temp.push_back(nums[j]);
            }
        }
        ans.push_back(temp);
    }
    for (auto x : ans)
    {
        if(x.size()>0)
        cout<<"[";
        for (auto y : x)
        {
            if(y==x[x.size()-1])
            cout << y <<"]";
            else
            cout << y <<", "; 
        }
        cout << endl;
    }
    return 0;
}
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

تحليل التعقيد لطباعة جميع المجموعات الفرعية

تعقيد الوقت

نقوم بتشغيل حلقتين متداخلتين ، واحدة من النطاق 2 ^ n والأخرى من النطاق n. لذا فإن التعقيد الزمني النهائي هو O (2 ^ n * n).

تعقيد الفضاء

هناك 2 ^ n-1 مجموعات فرعية ولكل مجموعة فرعية ، نحتاج إلى مساحة O (n) في المتوسط ​​بحيث يكون إجمالي تعقيد المساحة هو O (2 ^ n * n).

هل يمكننا تحسينه؟

نعم ، يمكننا تحسينه باستخدام التراجع ، دعنا نرى كيف!

الأسلوب 2: الحل التكراري باستخدام التراجع

نقوم بالتكرار على مصفوفة الأعداد ولكل موضع لدينا خياران ، إما أن نأخذ العنصر i أو نتخطاه.

خوارزمية

  1. قم بإنشاء دالة تأخذ الوسيطات ، مصفوفة الإجابة النهائية ، مصفوفة المجموعة الفرعية الحالية ، مصفوفة الإدخال ، ومتغير "فهرس" يشير إلى العنصر الحالي في مصفوفة الأعداد.
  2. الشرط الأساسي: إذا كان "الفهرس" مساويًا لحجم مصفوفة الأعداد ، فقم بإضافة مصفوفة المجموعة الفرعية الحالية إلى الإجابة النهائية لأننا الآن لا نستطيع اجتياز مصفوفة الأعداد بعد الآن.
  3. لدينا خياران الآن
    1. تخطي العنصر الحالي واستدعاء الدالة العودية مع الفهرس + 1 وستظل جميع الوسائط الأخرى كما هي.
    2. أضف العنصر الحالي إلى المجموعة الفرعية الحالية واستدع الدالة العودية باستخدام الفهرس +1 والوسيطات الأخرى. بعد استدعاء الدالة العودية ، قم بخطوة التراجع عن طريق إزالة العنصر الأخير من المجموعة الفرعية الحالية.
  4. اطبع الإجابة النهائية.

افهم بقدوة

لنأخذ مصفوفة الإدخال = [1,2,3،XNUMX،XNUMX]

ثم ستبدو شجرة العودية كما يلي:

مجموعة فرعية Leetcode

في الشجرة أعلاه ، المجموعة الفرعية (i) هي الوظيفة العودية حيث تشير i إلى الفهرس الحالي.

تنفيذ طباعة جميع المجموعات الفرعية

برنامج C ++ لـ Subset Leetcode

#include <bits/stdc++.h>
using namespace std;
void subsets(vector<vector<int>> &ans, vector<int> &temp, vector<int> &nums, int i)
{
    if (i == nums.size())
    {
        ans.push_back(temp);
        return;
    }
    subsets(ans, temp, nums, i + 1);
    temp.push_back(nums[i]);
    subsets(ans, temp, nums, i + 1);
    temp.pop_back();
    return;
}
int main()
{
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> ans;
    vector<int> temp;
    subsets(ans, temp, nums, 0);
    for (auto x : ans)
    {
        if(x.size()>0)
        cout<<"[";
        for (auto y : x)
        {
            if(y==x[x.size()-1])
            cout << y <<"]";
            else
            cout << y <<", "; 
        }
        cout << endl;
    }
    return 0;
}
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]

برنامج JAVA لمجموعة فرعية Leetcode

import java.util.*; 
public class Main
{
    static List<List<Integer>> res;
    public static void subsets(int[] nums,int index,List<Integer> list){
        if(index==nums.length-1){
            res.add(new ArrayList<Integer>(list));
            list.add(nums[index]);
            res.add(new ArrayList<Integer>(list));
            list.remove(list.size()-1);
            return;
        }
        subsets(nums,index+1,list);
        list.add(nums[index]);
        subsets(nums,index+1,list);
        list.remove(list.size()-1);
    }
  public static void main(String[] args) {
      res = new ArrayList<>();
      int[] nums={2, 3, 4};
      List<Integer> list = new ArrayList<Integer>();
      subsets(nums, 0, list);
      for(List<Integer> subset:res){
          for(int i: subset){
              System.out.print(i+", ");
          }
            System.out.println();
      }
  }
}

4, 
3, 
3, 4, 
2, 
2, 4, 
2, 3, 
2, 3, 4, 

تحليل التعقيد لمجموعة فرعية Leetcode

تعقيد الوقت

لكل فهرس ، نجري نداءين عوديين وهناك n من العناصر لذا فإن تعقيد الوقت الإجمالي هو O (2 ^ n).

تعقيد الفضاء

هناك 2 ^ n-1 مجموعات فرعية ولكل مجموعة فرعية ، نحتاج إلى مساحة O (n) في المتوسط ​​بحيث يكون إجمالي تعقيد المساحة هو O (2 ^ n * n).

المراجع