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:
- dp → todas las sumas que se produjeron antes del elemento a[i]
- dp << a[i] → desplazando todas las sumas por a[i], es decir, sumando a[i] a todas las sumas.
- 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).
- Ahora, si obtenemos un elemento 3, también podríamos hacer 5 y 7 sumando 2 y 4 respectivamente.
- Esto puede ser denotado por 010100000 que es equivalente a (000010100) << 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 :
- El tamaño del conjunto de bits debe ser una constante, esto a veces es un inconveniente, ya que podemos desperdiciar algo de espacio.
- 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.
- 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