Imprimir sumas de todos los subconjuntos de un conjunto dado

Dada una array de enteros, imprima las sumas de todos los subconjuntos en ella. Las sumas de salida se pueden imprimir en cualquier orden.

Ejemplos: 

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

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

Método 1 (Recursivo) 
Podemos resolver este problema recursivamente. Hay un total de 2 ⁿ subconjuntos. Para cada elemento, consideramos dos opciones, lo incluimos en un subconjunto y no lo incluimos en un subconjunto. A continuación se muestra una solución recursiva basada en esta idea.  

// C++ program to print sums of all possible
// subsets.
#include <bits/stdc++.h>
using namespace std;
 
// Prints sums of all subsets of arr[l..r]
void subsetSums(int arr[], int l, int r, int sum = 0)
{
    // Print current subset
    if (l > r) {
        cout << sum << " ";
        return;
    }
 
    // Subset including arr[l]
    subsetSums(arr, l + 1, r, sum + arr[l]);
 
    // Subset excluding arr[l]
    subsetSums(arr, l + 1, r, sum);
}
 
// Driver code
int main()
{
    int arr[] = { 5, 4, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    subsetSums(arr, 0, n - 1);
    return 0;
}

// Java program to print sums
// of all possible subsets.
import java.io.*;
 
class GFG {
 
    // Prints sums of all
    // subsets of arr[l..r]
    static void subsetSums(int[] arr, int l, int r, int sum)
    {
 
        // Print current subset
        if (l > r) {
            System.out.print(sum + " ");
            return;
        }
 
        // Subset including arr[l]
        subsetSums(arr, l + 1, r, sum + arr[l]);
 
        // Subset excluding arr[l]
        subsetSums(arr, l + 1, r, sum);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = { 5, 4, 3 };
        int n = arr.length;
 
        subsetSums(arr, 0, n - 1, 0);
    }
}
 
// This code is contributed by anuj_67

# Python3 program to print sums of
# all possible subsets.
 
# Prints sums of all subsets of arr[l..r]
 
 
def subsetSums(arr, l, r, sum=0):
 
    # Print current subset
    if l > r:
        print(sum, end=" ")
        return
 
    # Subset including arr[l]
    subsetSums(arr, l + 1, r, sum + arr[l])
 
    # Subset excluding arr[l]
    subsetSums(arr, l + 1, r, sum)
 
 
# Driver code
arr = [5, 4, 3]
n = len(arr)
subsetSums(arr, 0, n - 1)
 
# This code is contributed by Shreyanshi Arun.

// C# program to print sums of all possible
// subsets.
using System;
 
class GFG {
 
    // Prints sums of all subsets of
    // arr[l..r]
    static void subsetSums(int[] arr, int l, int r, int sum)
    {
 
        // Print current subset
        if (l > r) {
            Console.Write(sum + " ");
            return;
        }
 
        // Subset including arr[l]
        subsetSums(arr, l + 1, r, sum + arr[l]);
 
        // Subset excluding arr[l]
        subsetSums(arr, l + 1, r, sum);
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 5, 4, 3 };
        int n = arr.Length;
 
        subsetSums(arr, 0, n - 1, 0);
    }
}
 
// This code is contributed by anuj_67

<?php
// PHP program to print sums
// of all possible subsets.
 
// Prints sums of all
// subsets of arr[l..r]
function subsetSums($arr, $l,
                    $r, $sum = 0)
{
    // Print current subset
    if ($l > $r)
    {
        echo $sum , " ";
        return;
    }
 
    // Subset including arr[l]
    subsetSums($arr, $l + 1, $r,
               $sum + $arr[$l]);
 
    // Subset excluding arr[l]
    subsetSums($arr, $l + 1, $r, $sum);
}
 
// Driver code
$arr = array(5, 4, 3);
$n = count($arr);
 
subsetSums($arr, 0, $n - 1);
 
// This code is contributed by anuj_67.
?>

<script>
// Javascript program to program to print
// sums of all possible subsets.
 
// Prints sums of all
// subsets of arr[l..r]
function subsetSums(arr, l, r, sum)
{
     
    // Print current subset
    if (l > r)
    {
        document.write(sum + " ");
        return;
    }
   
    // Subset including arr[l]
    subsetSums(arr, l + 1, r,
               sum + arr[l]);
                
    // Subset excluding arr[l]
    subsetSums(arr, l + 1, r, sum);
}
     
// Driver code
let arr = [5, 4, 3];
let n = arr.length;
 
subsetSums(arr, 0, n - 1, 0);
 
// This code is contributed by code_hunt
     
</script>

Producción : 

12 9 8 5 7 4 3 0

Complejidad del tiempo: O(2^n) 

Espacio Auxiliar : O(n)

Método 2 (iterativo) 
Como se discutió anteriormente, hay un total de 2 ⁿ subconjuntos. La idea es generar un ciclo de 0 a 2 ⁿ – 1. Para cada número, elija todos los elementos de la array que correspondan a 1 en representación binaria del número actual.

// Iterative C++ program to print sums of all
// possible subsets.
#include <bits/stdc++.h>
using namespace std;
 
// Prints sums of all subsets of array
void subsetSums(int arr[], int n)
{
    // There are total 2^n subsets
    long long total = 1 << n;
 
    // Consider all numbers from 0 to 2^n - 1
    for (long long i = 0; i < total; i++) {
        long long sum = 0;
 
        // Consider binary representation of
        // current i to decide which elements
        // to pick.
        for (int j = 0; j < n; j++)
            if (i & (1 << j))
                sum += arr[j];
 
        // Print sum of picked elements.
        cout << sum << " ";
    }
}
 
// Driver code
int main()
{
    int arr[] = { 5, 4, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    subsetSums(arr, n);
    return 0;
}

// Iterative Java program to print sums of all
// possible subsets.
import java.util.*;
 
class GFG {
 
    // Prints sums of all subsets of array
    static void subsetSums(int arr[], int n)
    {
 
        // There are total 2^n subsets
        int total = 1 << n;
 
        // Consider all numbers from 0 to 2^n - 1
        for (int i = 0; i < total; i++) {
            int sum = 0;
 
            // Consider binary representation of
            // current i to decide which elements
            // to pick.
            for (int j = 0; j < n; j++)
                if ((i & (1 << j)) != 0)
                    sum += arr[j];
 
            // Print sum of picked elements.
            System.out.print(sum + " ");
        }
    }
 
    // Driver code
    public static void main(String args[])
    {
        int arr[] = new int[] { 5, 4, 3 };
        int n = arr.length;
 
        subsetSums(arr, n);
    }
}
 
// This code is contributed by spp____

# Iterative Python3 program to print sums of all possible subsets
 
# Prints sums of all subsets of array
def subsetSums(arr, n):
    # There are total 2^n subsets
    total = 1 << n
 
    # Consider all numbers from 0 to 2^n - 1
    for i in range(total):
       Sum = 0
 
       # Consider binary representation of
       # current i to decide which elements
       # to pick.
       for j in range(n):
          if ((i & (1 << j)) != 0):
              Sum += arr[j]
 
       # Print sum of picked elements.
       print(Sum, "", end = "")
 
arr = [ 5, 4, 3 ]
n = len(arr)
 
subsetSums(arr, n);
 
# This code is contributed by mukesh07.

// Iterative C# program to print sums of all
// possible subsets.
using System;
class GFG {
     
    // Prints sums of all subsets of array
    static void subsetSums(int[] arr, int n)
    {
  
        // There are total 2^n subsets
        int total = 1 << n;
  
        // Consider all numbers from 0 to 2^n - 1
        for (int i = 0; i < total; i++) {
            int sum = 0;
  
            // Consider binary representation of
            // current i to decide which elements
            // to pick.
            for (int j = 0; j < n; j++)
                if ((i & (1 << j)) != 0)
                    sum += arr[j];
  
            // Print sum of picked elements.
            Console.Write(sum + " ");
        }
    }
     
  static void Main() {
    int[] arr = { 5, 4, 3 };
    int n = arr.Length;
     
    subsetSums(arr, n);
  }
}
 
// This code is contributed by divyesh072019.

<?php
// Iterative PHP program to print
// sums of all possible subsets.
 
// Prints sums of all subsets of array
function subsetSums($arr, $n)
{
     
        // There are total 2^n subsets
        $total = 1 << $n;
 
    // Consider all numbers
    // from 0 to 2^n - 1
    for ($i = 0; $i < $total; $i++)
    {
        $sum = 0;
 
        // Consider binary representation of
        // current i to decide which elements
        // to pick.
        for ($j = 0; $j < $n; $j++)
            if ($i & (1 << $j))
                $sum += $arr[$j];
 
        // Print sum of picked elements.
        echo $sum , " ";
    }
}
 
    // Driver code
    $arr = array(5, 4, 3);
    $n = sizeof($arr);
    subsetSums($arr, $n);
     
// This Code is Contributed by ajit
?>

<script>
 
    // Iterative Javascript program to print sums of all
    // possible subsets.
     
    // Prints sums of all subsets of array
    function subsetSums(arr, n)
    {
 
        // There are total 2^n subsets
        let total = 1 << n;
 
        // Consider all numbers from 0 to 2^n - 1
        for(let i = 0; i < total; i++)
        {
           let sum = 0;
 
           // Consider binary representation of
           // current i to decide which elements
           // to pick.
           for(let j = 0; j < n; j++)
              if ((i & (1 << j)) != 0)
                  sum += arr[j];
 
           // Print sum of picked elements.
           document.write(sum + " ");
        }
    }
     
    let arr = [ 5, 4, 3 ];
    let n = arr.length;
  
    subsetSums(arr, n);
     
</script>

Producción : 

0 5 4 9 3 8 7 12 

Complejidad de tiempo: O( )
Espacio auxiliar: O(1) 
Gracias a cfh por sugerir la solución iterativa anterior en un comentario.
Nota: en realidad, no hemos creado subconjuntos para encontrar sus sumas, sino que solo hemos usado la recursividad para encontrar la suma de subconjuntos no contiguos del conjunto dado.

Las técnicas mencionadas anteriormente se pueden usar para realizar varias operaciones en subconjuntos como multiplicación, división, XOR, OR, etc., sin crear y almacenar los subconjuntos y, por lo tanto, hacer que la memoria del programa sea eficiente. 
Este artículo es una contribución de Aditya Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.