Encuentre todas las sumas distintas de subconjuntos (o subsecuencias) de una array

Dado un conjunto de enteros, encuentre una suma distinta que pueda generarse a partir de los subconjuntos de los conjuntos dados e imprímala en orden creciente. Se da que la suma de los elementos de la array es pequeña.

Ejemplos:  

Input  : arr[] = {1, 2, 3}
Output : 0 1 2 3 4 5 6
Distinct subsets of given set are
{}, {1}, {2}, {3}, {1,2}, {2,3}, 
{1,3} and {1,2,3}.  Sums of these
subsets are 0, 1, 2, 3, 3, 5, 4, 6
After removing duplicates, we get
0, 1, 2, 3, 4, 5, 6  

Input : arr[] = {2, 3, 4, 5, 6}
Output : 0 2 3 4 5 6 7 8 9 10 11 12 
         13 14 15 16 17 18 20

Input : arr[] = {20, 30, 50}
Output : 0 20 30 50 70 80 100

La solución ingenua para este problema es generar todos los subconjuntos, almacenar sus sumas en un conjunto hash y finalmente imprimir todas las claves del conjunto hash.  

C++

// C++ program to print distinct subset sums of
// a given array.
#include<bits/stdc++.h>
using namespace std;
 
// sum denotes the current sum of the subset
// currindex denotes the index we have reached in
// the given array
void distSumRec(int arr[], int n, int sum,
                int currindex, unordered_set<int> &s)
{
    if (currindex > n)
        return;
 
    if (currindex == n)
    {
        s.insert(sum);
        return;
    }
 
    distSumRec(arr, n, sum + arr[currindex],
                            currindex+1, s);
    distSumRec(arr, n, sum, currindex+1, s);
}
 
// This function mainly calls recursive function
// distSumRec() to generate distinct sum subsets.
// And finally prints the generated subsets.
void printDistSum(int arr[], int n)
{
    unordered_set<int> s;
    distSumRec(arr, n, 0, 0, s);
 
    // Print the result
    for (auto i=s.begin(); i!=s.end(); i++)
        cout << *i << " ";
}
 
// Driver code
int main()
{
    int arr[] = {2, 3, 4, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    printDistSum(arr, n);
    return 0;
}

Java

// Java program to print distinct
// subset sums of a given array.
import java.io.*;
import java.util.*;
 
class GFG
{
    // sum denotes the current sum
    // of the subset currindex denotes
    // the index we have reached in
    // the given array
    static void distSumRec(int arr[], int n, int sum,
                          int currindex, HashSet<Integer> s)
    {
        if (currindex > n)
            return;
 
        if (currindex == n) {
            s.add(sum);
            return;
        }
 
        distSumRec(arr, n, sum + arr[currindex],
                    currindex + 1, s);
        distSumRec(arr, n, sum, currindex + 1, s);
    }
 
    // This function mainly calls
    // recursive function distSumRec()
    // to generate distinct sum subsets.
    // And finally prints the generated subsets.
    static void printDistSum(int arr[], int n)
    {
        HashSet<Integer> s = new HashSet<>();
        distSumRec(arr, n, 0, 0, s);
 
        // Print the result
        for (int i : s)
            System.out.print(i + " ");
    }
     
    //Driver code
    public static void main(String[] args)
    {
        int arr[] = { 2, 3, 4, 5, 6 };
        int n = arr.length;
        printDistSum(arr, n);
    }
}
 
// This code is contributed by Gitanjali.

Python3

# Python 3 program to print distinct subset sums of
# a given array.
 
# sum denotes the current sum of the subset
# currindex denotes the index we have reached in
# the given array
def distSumRec(arr, n, sum, currindex, s):
    if (currindex > n):
        return
 
    if (currindex == n):
        s.add(sum)
        return
 
    distSumRec(arr, n, sum + arr[currindex], currindex+1, s)
    distSumRec(arr, n, sum, currindex+1, s)
 
# This function mainly calls recursive function
# distSumRec() to generate distinct sum subsets.
# And finally prints the generated subsets.
def printDistSum(arr,n):
    s = set()
    distSumRec(arr, n, 0, 0, s)
 
    # Print the result
    for i in s:
        print(i,end = " ")
 
# Driver code
if __name__ == '__main__':
    arr = [2, 3, 4, 5, 6]
    n = len(arr)
    printDistSum(arr, n)
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to print distinct
// subset sums of a given array.
using System;
using System.Collections.Generic;
 
class GFG
{
    // sum denotes the current sum
    // of the subset currindex denotes
    // the index we have reached in
    // the given array
    static void distSumRec(int []arr, int n, int sum,
                        int currindex, HashSet<int> s)
    {
        if (currindex > n)
            return;
 
        if (currindex == n)
        {
            s.Add(sum);
            return;
        }
 
        distSumRec(arr, n, sum + arr[currindex],
                    currindex + 1, s);
        distSumRec(arr, n, sum, currindex + 1, s);
    }
 
    // This function mainly calls
    // recursive function distSumRec()
    // to generate distinct sum subsets.
    // And finally prints the generated subsets.
    static void printDistSum(int []arr, int n)
    {
        HashSet<int> s = new HashSet<int>();
        distSumRec(arr, n, 0, 0, s);
 
        // Print the result
        foreach (int i in s)
            Console.Write(i + " ");
    }
     
    // Driver code
    public static void Main()
    {
        int []arr = { 2, 3, 4, 5, 6 };
        int n = arr.Length;
        printDistSum(arr, n);
    }
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
// Javascript program to print distinct
// subset sums of a given array.
     
    // sum denotes the current sum
    // of the subset currindex denotes
    // the index we have reached in
    // the given array
    function distSumRec(arr,n,sum,currindex,s)
    {
        if (currindex > n)
            return;
   
        if (currindex == n) {
            s.add(sum);
            return;
        }
   
        distSumRec(arr, n, sum + arr[currindex],
                    currindex + 1, s);
        distSumRec(arr, n, sum, currindex + 1, s);
    }
     
     
    // This function mainly calls
    // recursive function distSumRec()
    // to generate distinct sum subsets.
    // And finally prints the generated subsets.
    function printDistSum(arr,n)
    {
        let s=new Set();
        distSumRec(arr, n, 0, 0, s);
        let s1=[...s]
          s1.sort(function(a,b){return a-b;})
        // Print the result
        for (let [key, value] of s1.entries())
            document.write(value + " ");
    }
     
    //Driver code
    let arr=[2, 3, 4, 5, 6 ];
    let n = arr.length;
    printDistSum(arr, n);
     
     
    // This code is contributed by unknown2108
</script>

Producción:  

0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20

La complejidad temporal del enfoque recursivo ingenuo anterior es O(2 n ).

La complejidad temporal del problema anterior se puede mejorar utilizando la programación dinámica , especialmente cuando la suma de los elementos dados es pequeña. Podemos hacer una tabla dp con filas que contengan el tamaño de la array y el tamaño de la columna será la suma de todos los elementos de la array.  

C++

// C++ program to print distinct subset sums of
// a given array.
#include<bits/stdc++.h>
using namespace std;
 
// Uses Dynamic Programming to find distinct
// subset sums
void printDistSum(int arr[], int n)
{
    int sum = 0;
    for (int i=0; i<n; i++)
        sum += arr[i];
 
    // dp[i][j] would be true if arr[0..i-1] has
    // a subset with sum equal to j.
    bool dp[n+1][sum+1];
    memset(dp, 0, sizeof(dp));
 
    // There is always a subset with 0 sum
    for (int i=0; i<=n; i++)
        dp[i][0] = true;
 
    // Fill dp[][] in bottom up manner
    for (int i=1; i<=n; i++)
    {
        dp[i][arr[i-1]] = true;
        for (int j=1; j<=sum; j++)
        {
            // Sums that were achievable
            // without current array element
            if (dp[i-1][j] == true)
            {
                dp[i][j] = true;
                dp[i][j + arr[i-1]] = true;
            }
        }
    }
 
    // Print last row elements
    for (int j=0; j<=sum; j++)
        if (dp[n][j]==true)
            cout << j << " ";
}
 
 
// Driver code
int main()
{
    int arr[] = {2, 3, 4, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    printDistSum(arr, n);
    return 0;
}

Java

// Java program to print distinct
// subset sums of a given array.
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Uses Dynamic Programming to
    // find distinct subset sums
    static void printDistSum(int arr[], int n)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += arr[i];
 
        // dp[i][j] would be true if arr[0..i-1]
        // has a subset with sum equal to j.
        boolean[][] dp = new boolean[n + 1][sum + 1];
 
        // There is always a subset with 0 sum
        for (int i = 0; i <= n; i++)
            dp[i][0] = true;
 
        // Fill dp[][] in bottom up manner
        for (int i = 1; i <= n; i++)
        {
            dp[i][arr[i - 1]] = true;
            for (int j = 1; j <= sum; j++)
            {
                // Sums that were achievable
                // without current array element
                if (dp[i - 1][j] == true)
                {
                    dp[i][j] = true;
                    dp[i][j + arr[i - 1]] = true;
                }
            }
        }
 
        // Print last row elements
        for (int j = 0; j <= sum; j++)
            if (dp[n][j] == true)
                System.out.print(j + " ");
    }
 
        // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 2, 3, 4, 5, 6 };
        int n = arr.length;
        printDistSum(arr, n);
    }
}
 
// This code is contributed by Gitanjali.

Python3

# Python3 program to print distinct subset
# Sums of a given array.
 
# Uses Dynamic Programming to find
# distinct subset Sums
def printDistSum(arr, n):
 
    Sum = sum(arr)
     
    # dp[i][j] would be true if arr[0..i-1]
    # has a subset with Sum equal to j.
    dp = [[False for i in range(Sum + 1)]
                 for i in range(n + 1)]
                  
    # There is always a subset with 0 Sum
    for i in range(n + 1):
        dp[i][0] = True
 
    # Fill dp[][] in bottom up manner
    for i in range(1, n + 1):
 
        dp[i][arr[i - 1]] = True
 
        for j in range(1, Sum + 1):
             
            # Sums that were achievable
            # without current array element
            if (dp[i - 1][j] == True):
                dp[i][j] = True
                dp[i][j + arr[i - 1]] = True
             
    # Print last row elements
    for j in range(Sum + 1):
        if (dp[n][j] == True):
            print(j, end = " ")
 
# Driver code
arr = [2, 3, 4, 5, 6]
n = len(arr)
printDistSum(arr, n)
 
# This code is contributed
# by mohit kumar

C#

// C# program to print distinct
// subset sums of a given array.
using System;
  
class GFG {
  
    // Uses Dynamic Programming to
    // find distinct subset sums
    static void printDistSum(int []arr, int n)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += arr[i];
  
        // dp[i][j] would be true if arr[0..i-1]
        // has a subset with sum equal to j.
        bool [,]dp = new bool[n + 1,sum + 1];
  
        // There is always a subset with 0 sum
        for (int i = 0; i <= n; i++)
            dp[i,0] = true;
  
        // Fill dp[][] in bottom up manner
        for (int i = 1; i <= n; i++)
        {
            dp[i,arr[i - 1]] = true;
            for (int j = 1; j <= sum; j++)
            {
                // Sums that were achievable
                // without current array element
                if (dp[i - 1,j] == true)
                {
                    dp[i,j] = true;
                    dp[i,j + arr[i - 1]] = true;
                }
            }
        }
  
        // Print last row elements
        for (int j = 0; j <= sum; j++)
            if (dp[n,j] == true)
                Console.Write(j + " ");
    }
  
    // Driver code
    public static void Main()
    {
        int []arr = { 2, 3, 4, 5, 6 };
        int n = arr.Length;
        printDistSum(arr, n);
    }
}
  
// This code is contributed by nitin mittal.

Javascript

<script>
 
// Javascript program to print distinct
// subset sums of a given array.
 
// Uses Dynamic Programming to find
// distinct subset sums
function printDistSum(arr, n)
{
    var sum = 0;
    for(var i = 0; i < n; i++)
        sum += arr[i];
 
    // dp[i][j] would be true if arr[0..i-1] has
    // a subset with sum equal to j.
    var dp = Array.from(
        Array(n + 1), () => Array(sum + 1).fill(0));
 
    // There is always a subset with 0 sum
    for(var i = 0; i <= n; i++)
        dp[i][0] = true;
 
    // Fill dp[][] in bottom up manner
    for(var i = 1; i <= n; i++)
    {
        dp[i][arr[i - 1]] = true;
        for(var j = 1; j <= sum; j++)
        {
             
            // Sums that were achievable
            // without current array element
            if (dp[i - 1][j] == true)
            {
                dp[i][j] = true;
                dp[i][j + arr[i - 1]] = true;
            }
        }
    }
 
    // Print last row elements
    for(var j = 0; j <= sum; j++)
        if (dp[n][j] == true)
            document.write(j + " ");
}
 
// Driver code
var arr = [ 2, 3, 4, 5, 6 ];
var n = arr.length;
 
printDistSum(arr, n);
 
// This code is contributed by importantly
 
</script>

Producción:  

0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20

La complejidad temporal del enfoque anterior es O(n*sum) donde n es el tamaño de la array y sum es la suma de todos los enteros de la array.

Enfoque de conjunto de bits optimizado

dp = dp | dp << a[i]

El fragmento de código anterior hace lo mismo que la solución ingenua, donde dp es una máscara de bits (usaremos un conjunto de bits). Veamos cómo:

  1. dp → todas las sumas que se produjeron antes del elemento a[i]
  2. dp << a[i] → desplazando todas las sumas por a[i], es decir, sumando a[i] a todas las sumas.
    1. Por ejemplo, supongamos que inicialmente la máscara de bits era 000010100 , lo que significa que solo podríamos generar 2 y 4 (contar desde la derecha).
    2. Ahora, si obtenemos un elemento 3, también podríamos hacer 5 y 7 sumando 2 y 4 respectivamente.
    3. Esto puede ser denotado por 010100000 que es equivalente a (000010100) << 3
  3. doble penetración | (dp << a[i])000010100 | 010100000 = 010110100 Esta es la unión de las dos sumas anteriores que representan qué sumas son posibles, a saber, 2, 4, 5 y 7.

Mochila optimizada para bitset

C++

// C++ Program to Demonstrate Bitset Optimised Knapsack
// Solution
 
#include <bits/stdc++.h>
using namespace std;
 
// Driver Code
int main()
{
    // Input Vector
    vector<int> a = { 2, 3, 4, 5, 6 };
 
    // we have to make a constant size for bit-set
    // and to be safe keep it significantly high
    int n = a.size();
    const int mx = 40;
 
    // bitset of size mx, dp[i] is 1 if sum i is possible
    // and 0 otherwise
    bitset<mx> dp;
    // sum 0 is always possible
    dp[0] = 1;
 
    // dp transitions as explained in article
    for (int i = 0; i < n; ++i) {
        dp |= dp << a[i];
    }
 
    // print all the  1s in bit-set, this will be the
    // all the unique sums possible
    for (int i = 0; i <= mx; i++) {
        if (dp[i] == 1)
            cout << i << " ";
    }
}
 
// code is contributed by sarvjot singh
Producción

0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 

La complejidad del tiempo también parece ser O ( N * S ). Porque si hubiéramos usado una array en lugar de un conjunto de bits, el cambio habría tomado un tiempo lineal O( S ). Sin embargo, la operación de cambio (y casi todas) en el conjunto de bits toma tiempo O ( S / W ). Donde W es el tamaño de palabra del sistema, generalmente es de 32 o 64 bits. Por lo tanto, la complejidad del tiempo final se convierte en O ( N * S / W )

Algunos puntos importantes :

  1. El tamaño del conjunto de bits debe ser una constante, esto a veces es un inconveniente, ya que podemos desperdiciar algo de espacio.
  2. Bitset se puede pensar en una array donde cada elemento se ocupa de los elementos W. Por ejemplo , 010110100 es equivalente a {2, 6, 4} en un sistema hipotético con tamaño de palabra W = 3.
  3. La solución de mochila optimizada de Bitset redujo la complejidad del tiempo en un factor de W , que a veces es suficiente para obtener CA.

Este artículo es una contribución de Karan Goyal . 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 contribuir@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.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *