Рубрики

Вывести суммы всех подмножеств данного набора

Учитывая массив целых чисел, выведите суммы всех подмножеств в нем. Выходные суммы могут быть напечатаны в любом порядке.

Примеры :

Input : arr[] = {2, 3}
Output: 0 2 3 5

Input : arr[] = {2, 4, 5}
Output : 0 2 4 5 6 7 9 11

Метод 1 (рекурсивный)
Мы можем рекурсивно решить эту проблему. Всего есть 2 n подмножеств. Для каждого элемента мы рассматриваем два варианта, мы включаем его в подмножество и не включаем его в подмножество. Ниже приведено рекурсивное решение, основанное на этой идее.

C ++

// C ++ программа для печати сумм всех возможных
// подмножества.
#include<bits/stdc++.h>

using namespace std;

  
// Печатает суммы всех подмножеств arr [l..r]

void subsetSums(int arr[], int l, int r,

                int sum=0)

{

    // Распечатать текущее подмножество

    if (l > r)

    {

        cout << sum << " ";

        return;

    }

  

    // Подмножество, включая arr [l]

    subsetSums(arr, l+1, r, sum+arr[l]);

  

    // Подмножество, исключая arr [l]

    subsetSums(arr, l+1, r, sum);

}

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

int main()

{

    int arr[] = {5, 4, 3};

    int n = sizeof(arr)/sizeof(arr[0]);

  

    subsetSums(arr, 0, n-1);

    return 0;

}

Джава

// Java-программа для печати сумм
// из всех возможных подмножеств.

import java .io.*;

  

class GFG 

{

      

    // Печатает суммы всех

    // подмножества arr [l..r]

    static void subsetSums(int []arr, int l,

                            int r, int sum )

    {

          

        // Распечатать текущее подмножество

        if (l > r)

        {

            System.out.print(sum + " ");

            return;

        }

      

        // Подмножество, включая arr [l]

        subsetSums(arr, l + 1, r, 

                   sum + arr[l]);

      

        // Подмножество, исключая arr [l]

        subsetSums(arr, l + 1, r, sum);

    }

      

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

    public static void main (String[] args)

    {

        int []arr = {5, 4, 3};

        int n = arr.length;

      

        subsetSums(arr, 0, n - 1, 0);

    }

}

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

python3

# Python3 программа для печати сумм
# все возможные подмножества.

  
# Печатает суммы всех подмножеств arr [l..r]

def subsetSums(arr, l, r, sum = 0):

      

    # Распечатать текущее подмножество

    if l > r:

        print (sum, end = " ")

        return

  

    # Подмножество, включая arr [l]

    subsetSums(arr, l + 1, r, sum + arr[l])

  

    # Подмножество, исключая arr [l]

    subsetSums(arr, l + 1, r, sum)

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

arr = [5, 4, 3]

n = len(arr)

subsetSums(arr, 0, n - 1)

  
# Этот код предоставлен Shreyanshi Arun.

C #

// C # программа для печати сумм всех возможных
// подмножества.

using System;

  

class GFG {

      

    // Печатает суммы всех подмножеств

    // arr [l..r]

    static void subsetSums(int []arr, int l,

                            int r, int sum )

    {

          

        // Распечатать текущее подмножество

        if (l > r)

        {

            Console.Write(sum + " ");

            return;

        }

      

        // Подмножество, включая arr [l]

        subsetSums(arr, l+1, r, sum + arr[l]);

      

        // Подмножество, исключая arr [l]

        subsetSums(arr, l+1, r, sum);

    }

      

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

    public static void Main ()

    {

        int []arr = {5, 4, 3};

        int n = arr.Length;

      

        subsetSums(arr, 0, n-1,0);

    }

}

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

PHP

<?php
// PHP программа для печати сумм
// из всех возможных подмножеств.

  
// Печатает суммы всех
// подмножества arr [l..r]

function subsetSums($arr, $l

                    $r, $sum = 0)

{

    // Распечатать текущее подмножество

    if ($l > $r)

    {

        echo $sum , " ";

        return;

    }

  

    // Подмножество, включая arr [l]

    subsetSums($arr, $l + 1, $r

               $sum + $arr[$l]);

  

    // Подмножество, исключая arr [l]

    subsetSums($arr, $l + 1, $r, $sum);

}

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

$arr = array(5, 4, 3);

$n = count($arr);

  

subsetSums($arr, 0, $n - 1);

  
// Этот код предоставлен anuj_67.
?>


Выход :

12 9 8 5 7 4 3 0

Метод 2 (итеративный)
Как обсуждалось выше, всего имеется 2 n подмножеств. Идея состоит в том, чтобы сгенерировать цикл от 0 до 2 n — 1. Для каждого числа выберите все элементы массива, которые соответствуют 1 в двоичном представлении текущего числа.

C ++

// Итеративная программа C ++ для печати сумм всех
// возможные подмножества.
#include<bits/stdc++.h>

using namespace std;

  
// Печатает суммы всех подмножеств массива

void subsetSums(int arr[], int n)

{

    // Всего 2 ^ n подмножеств

    long long total = 1<<n;

  

    // Рассмотрим все числа от 0 до 2 ^ n - 1

    for (long long i=0; i<total; i++)

    {

        long long sum = 0;

  

        // Рассмотрим двоичное представление

        // текущий я, чтобы решить, какие элементы

        // подобрать.

        for (int j=0; j<n; j++)

            if (i & (1<<j))

                sum += arr[j];

  

        // Вывести сумму выбранных элементов.

        cout << sum << " ";

    }

}

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

int main()

{

    int arr[] = {5, 4, 3};

    int n = sizeof(arr)/sizeof(arr[0]);

  

    subsetSums(arr, n);

    return 0;

}

PHP

<?php
// Итеративная PHP-программа для печати
// суммы всех возможных подмножеств.

  
// Печатает суммы всех подмножеств массива

function subsetSums($arr, $n

      

        // Всего 2 ^ n подмножеств

        $total = 1 << $n

  

    // Рассмотрим все числа

    // от 0 до 2 ^ n - 1

    for ($i = 0; $i < $total; $i++) 

    

        $sum = 0; 

  

        // Рассмотрим двоичное представление

        // текущий я, чтобы решить, какие элементы

        // подобрать.

        for ($j = 0; $j < $n; $j++) 

            if ($i & (1 << $j)) 

                $sum += $arr[$j]; 

  

        // Вывести сумму выбранных элементов.

        echo $sum , " "

    

  

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

    $arr = array(5, 4, 3); 

    $n = sizeof($arr);

    subsetSums($arr, $n); 

      
// Этот код предоставлен ajit
?>


Выход :

0 5 4 9 3 8 7 12 

Спасибо cfh за предложенное выше итеративное решение в комментарии.

Примечание. На самом деле мы не создавали подмножества для поиска их сумм, мы просто использовали рекурсию, чтобы найти сумму несмежных подмножеств данного набора.

Вышеупомянутые методы могут использоваться для выполнения различных операций над подмножествами, такими как умножение, деление, XOR, OR и т. Д., Без фактического создания и сохранения подмножеств и, следовательно, повышения эффективности памяти программ.

Эта статья предоставлена Адитьей Гуптой . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме. Неправильно, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме

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

Вывести суммы всех подмножеств данного набора

0.00 (0%) 0 votes