Рубрики

Сумма подмножеств всех подмножеств массива | O (2 ^ N)

Для заданного массива arr [] длины N задача состоит в том, чтобы найти общую сумму подмножеств всех подмножеств массива.

Примеры:

Input: arr[] = {1, 1}
Output: 6
All possible subsets:
a) {} : 0
All the possible subsets of this subset
will be {}, Sum = 0
b) {1} : 1
All the possible subsets of this subset
will be {} and {1}, Sum = 0 + 1 = 1
c) {1} : 1
All the possible subsets of this subset
will be {} and {1}, Sum = 0 + 1 = 1
d) {1, 1} : 4
All the possible subsets of this subset
will be {}, {1}, {1} and {1, 1}, Sum = 0 + 1 + 1 + 2 = 4
Thus, ans = 0 + 1 + 1 + 4 = 6

Input: arr[] = {1, 4, 2, 12}
Output: 513

Подход: в этой статье будет обсуждаться подход с O (N * 2 N ) временной сложностью для решения данной проблемы.
Сначала сгенерируйте все возможные подмножества массива. Всего будет 2 N подмножеств. Затем для каждого подмножества найдите сумму всех его подмножеств.

При этом можно заметить, что в массиве длины L каждый элемент будет приходиться ровно 2 (L — 1) раза в сумме подмножеств. Таким образом, вклад каждого элемента будет в 2 (L — 1) раза больше его значений.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для суммирования всех подмножеств
// данный массив

void subsetSum(vector<int>& c, int& ans)

{

    int L = c.size();

    int mul = (int)pow(2, L - 1);

    for (int i = 0; i < c.size(); i++)

        ans += c[i] * mul;

}

  
// Функция для генерации подмножеств

void subsetGen(int* arr, int i, int n,

               int& ans, vector<int>& c)

{

    // Базовый вариант

    if (i == n) {

  

        // Находим сумму всех подмножеств

        // сгенерированного подмножества

        subsetSum(c, ans);

        return;

    }

  

    // Рекурсивно принимаю и отвергаю

    // текущий номер

    subsetGen(arr, i + 1, n, ans, c);

    c.push_back(arr[i]);

    subsetGen(arr, i + 1, n, ans, c);

    c.pop_back();

}

  
// Код драйвера

int main()

{

    int arr[] = { 1, 1 };

    int n = sizeof(arr) / sizeof(int);

  

    // Для сохранения финального ответа

    int ans = 0;

    vector<int> c;

  

    subsetGen(arr, 0, n, ans, c);

    cout << ans;

  

    return 0;

}

Джава

// Java реализация подхода

import java.util.*;

  

class GFG 

{

  
// Для сохранения финального ответа

static int ans;

  
// Функция для суммирования всех подмножеств
// данный массив

static void subsetSum(Vector<Integer> c)

{

    int L = c.size();

    int mul = (int)Math.pow(2, L - 1);

    for (int i = 0; i < c.size(); i++)

        ans += c.get(i) * mul;

}

  
// Функция для генерации подмножеств

static void subsetGen(int []arr, int i, 

                      int n, Vector<Integer> c)

{

    // Базовый вариант

    if (i == n) 

    {

  

        // Находим сумму всех подмножеств

        // сгенерированного подмножества

        subsetSum(c);

        return;

    }

  

    // Рекурсивно принимаю и отвергаю

    // текущий номер

    subsetGen(arr, i + 1, n, c);

    c.add(arr[i]);

    subsetGen(arr, i + 1, n, c);

    c.remove(0);

}

  
// Код драйвера

public static void main(String []args) 

{

    int arr[] = { 1, 1 };

    int n = arr.length;

  

    Vector<Integer> c = new Vector<Integer>();

  

    subsetGen(arr, 0, n, c);

    System.out.println(ans);

}
}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 реализация подхода

  
# сохранить ответ

c = []

ans = 0

  
# Функция для суммирования всех подмножеств
# заданный массив

def subsetSum():

    global ans

    L = len(c)

    mul = pow(2, L - 1)

    i = 0

    while ( i < len(c)):

        ans += c[i] * mul

        i += 1

          
# Функция для генерации подмножеств

def subsetGen(arr, i, n):

  

    # Базовый вариант

    if (i == n) :

  

        # Нахождение суммы всех подмножеств

        # сгенерированного подмножества

        subsetSum()

        return

      

    # Рекурсивное принятие и отклонение

    # текущий номер

    subsetGen(arr, i + 1, n)

    c.append(arr[i])

    subsetGen(arr, i + 1, n)

    c.pop()

  
# Код драйвера

if __name__ == "__main__"

  

    arr = [ 1, 1 ]

    n = len(arr)

  

    subsetGen(arr, 0, n)

    print (ans)

      
# Этот код предоставлен Арнабом Кунду

C #

// C # реализация подхода

using System;

using System.Collections.Generic; 

  

class GFG 

{

  
// Для сохранения финального ответа

static int ans;

  
// Функция для суммирования всех подмножеств
// данный массив

static void subsetSum(List<int> c)

{

    int L = c.Count;

    int mul = (int)Math.Pow(2, L - 1);

    for (int i = 0; i < c.Count; i++)

        ans += c[i] * mul;

}

  
// Функция для генерации подмножеств

static void subsetGen(int []arr, int i, 

                      int n, List<int> c)

{

    // Базовый вариант

    if (i == n) 

    {

  

        // Находим сумму всех подмножеств

        // сгенерированного подмножества

        subsetSum(c);

        return;

    }

  

    // Рекурсивно принимаю и отвергаю

    // текущий номер

    subsetGen(arr, i + 1, n, c);

    c.Add(arr[i]);

    subsetGen(arr, i + 1, n, c);

    c.RemoveAt(0);

}

  
// Код драйвера

public static void Main(String []args) 

{

    int []arr = { 1, 1 };

    int n = arr.Length;

  

    List<int> c = new List<int>();

  

    subsetGen(arr, 0, n, c);

    Console.WriteLine(ans);

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

6

Рекомендуемые посты:

Сумма подмножеств всех подмножеств массива | O (2 ^ N)

0.00 (0%) 0 votes