Підмножина Leetcode


Рівень складності Medium
Часто запитують у Амазонка Apple Bloomberg ByteDance Facebook Google Microsoft оракул
масив Зворотний трек Біт Маніпуляція бітами біти

У задачі Subset Leetcode ми подали набір різних цілих чисел, чисел, надрукували всі підмножини (набір потужностей).

Примітка: Набір рішень не повинен містити повторюваних підмножин.

Масив 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. Заявіть масив векторів “ans”, в яких ми будемо зберігати всі наші підмножини.
  2. Ініціалізуйте змінну n, яка представляє розмір масиву nums__.
  3. Запустіть цикл для I в діапазоні від 0 до 2n-1
    1. Ініціалізуйте масив “temp”, в якому ми будемо зберігати поточну підмножину.
    2. Запустіть цикл для j в діапазоні від 0 до n-1
      1. Якщо встановлений j-й біт I, додайте числа [i] до тимчасового масиву.
    3. Додайте масив “temp” до “ans”
  4. Друк остаточного масиву ans.

Реалізація для друку всіх підмножин

#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: Рекурсивне рішення із використанням зворотного відстеження

Ми перебираємо масив nums і для кожної позиції у нас є два варіанти: або взяти i-й елемент, або пропустити його.

Алгоритм

  1. Створіть функцію, яка приймає аргументи, остаточний масив відповідей, поточний масив підмножин, вхідний масив та змінну “index”, яка вказує на поточний елемент у масиві nums.
  2. Базова умова: Якщо “індекс” дорівнює розміру масиву nums, тоді додайте наш поточний масив підмножини до остаточної відповіді, оскільки тепер ми більше не можемо обходити масив nums.
  3. Зараз у нас є два варіанти вибору
    1. Пропустити поточний елемент і викликати рекурсивну функцію з індексом + 1, а всі інші аргументи залишаться незмінними.
    2. Додайте поточний елемент до поточного підмножини та викличте рекурсивну функцію з індексом +1 та іншими аргументами. Після виклику рекурсивної функції виконайте крок зворотного відстеження, видаливши останній елемент із поточної підмножини.
  4. Надрукуйте остаточну відповідь.

Зрозумійте на прикладі

Візьмемо вхідний масив nums = [1,2,3]

Тоді дерево рекурсії буде виглядати так:

Підмножина Leetcode

У наведеному вище дереві підмножина (i) - це рекурсивна функція, де i позначає поточний індекс.

Реалізація для друку всіх підмножин

Програма C ++ для підмножини 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

Часова складність

Для кожного індексу ми робимо 2 виклики рекурсії, і є n елементів, тому загальна складність часу дорівнює O (2 ^ n).

Космічна складність

Є 2 ^ n-1 підмножини, і для кожної підмножини нам в середньому потрібен O ​​(n) простір, тому загальна складність простору дорівнює O (2 ^ n * n).

посилання