Dada una array arr[] de longitud N , la tarea es encontrar la suma total de los subconjuntos de todos los subconjuntos de la array.
Ejemplos:
Entrada: arr[] = {1, 1}
Salida: 6
Todos los subconjuntos posibles:
a) {} : 0
Todos los subconjuntos posibles de este subconjunto
serán {}, Sum = 0
b) {1} : 1
Todos los subconjuntos posibles de este subconjunto
serán {} y {1}, Sum = 0 + 1 = 1
c) {1} : 1
Todos los posibles subconjuntos de este subconjunto
serán {} y {1}, Sum = 0 + 1 = 1
d ) {1, 1} : 4
Todos los subconjuntos posibles de este subconjunto
serán {}, {1}, {1} y {1, 1}, Suma = 0 + 1 + 1 + 2 = 4
Así, ans = 0 + 1 + 1 + 4 = 6
Entrada: arr[] = {1, 4, 2, 12}
Salida: 513
Enfoque: En este artículo, se discutirá un enfoque con complejidad de tiempo O(3 N ) para resolver el problema dado.
Primero, genere todos los subconjuntos posibles de la array. Habrá 2 N subconjuntos en total. Luego, para cada subconjunto, encuentre la suma de todos sus subconjuntos.
Ahora, comprendamos la complejidad temporal de esta solución.
Hay N C k subconjuntos de longitud K y el tiempo para encontrar los subconjuntos de una array de longitud K es 2 K .
Tiempo total = ( NC 1 * 2 1 ) + ( NC2 * 2 2 ) + … + ( N C k * K ) = 3 K
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to sum of all subsets of a
// given array
void subsetSum(vector<int>& c, int i,
int& ans, int curr)
{
// Base case
if (i == c.size()) {
ans += curr;
return;
}
// Recursively calling subsetSum
subsetSum(c, i + 1, ans, curr + c[i]);
subsetSum(c, i + 1, ans, curr);
}
// Function to generate the subsets
void subsetGen(int* arr, int i, int n,
int& ans, vector<int>& c)
{
// Base-case
if (i == n) {
// Finding the sum of all the subsets
// of the generated subset
subsetSum(c, 0, ans, 0);
return;
}
// Recursively accepting and rejecting
// the current number
subsetGen(arr, i + 1, n, ans, c);
c.push_back(arr[i]);
subsetGen(arr, i + 1, n, ans, c);
c.pop_back();
}
// Driver code
int main()
{
int arr[] = { 1, 1 };
int n = sizeof(arr) / sizeof(int);
// To store the final ans
int ans = 0;
vector<int> c;
subsetGen(arr, 0, n, ans, c);
cout << ans;
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static Vector<Integer> c = new Vector<>();
// To store the final ans
static int ans = 0;
// Function to sum of all subsets of a
// given array
static void subsetSum(int i, int curr)
{
// Base case
if (i == c.size())
{
ans += curr;
return;
}
// Recursively calling subsetSum
subsetSum(i + 1, curr + c.elementAt(i));
subsetSum(i + 1, curr);
}
// Function to generate the subsets
static void subsetGen(int[] arr, int i, int n)
{
// Base-case
if (i == n)
{
// Finding the sum of all the subsets
// of the generated subset
subsetSum(0, 0);
return;
}
// Recursively accepting and rejecting
// the current number
subsetGen(arr, i + 1, n);
c.add(arr[i]);
subsetGen(arr, i + 1, n);
c.remove(c.size() - 1);
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 1 };
int n = arr.length;
subsetGen(arr, 0, n);
System.out.println(ans);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of the approach # Function to sum of all subsets # of a given array c = [] ans = 0 def subsetSum(i, curr): global ans, c # Base case if (i == len(c)): ans += curr return # Recursively calling subsetSum subsetSum(i + 1, curr + c[i]) subsetSum(i + 1, curr) # Function to generate the subsets def subsetGen(arr, i, n): global ans, c # Base-case if (i == n): # Finding the sum of all the subsets # of the generated subset subsetSum(0, 0) return # Recursively accepting and rejecting # the current number subsetGen(arr, i + 1, n) c.append(arr[i]) subsetGen(arr, i + 1, n) del c[-1] # Driver code arr = [1, 1] n = len(arr) subsetGen(arr, 0, n) print(ans) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static List<int> c = new List<int>();
// To store the readonly ans
static int ans = 0;
// Function to sum of all subsets of a
// given array
static void subsetSum(int i, int curr)
{
// Base case
if (i == c.Count)
{
ans += curr;
return;
}
// Recursively calling subsetSum
subsetSum(i + 1, curr + c[i]);
subsetSum(i + 1, curr);
}
// Function to generate the subsets
static void subsetGen(int[] arr, int i, int n)
{
// Base-case
if (i == n)
{
// Finding the sum of all the subsets
// of the generated subset
subsetSum(0, 0);
return;
}
// Recursively accepting and rejecting
// the current number
subsetGen(arr, i + 1, n);
c.Add(arr[i]);
subsetGen(arr, i + 1, n);
c.RemoveAt(c.Count - 1);
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 1, 1 };
int n = arr.Length;
subsetGen(arr, 0, n);
Console.WriteLine(ans);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
var ans = 0;
var c = [];
// Function to sum of all subsets of a
// given array
function subsetSum(i, curr)
{
// Base case
if (i == c.length) {
ans += curr;
return;
}
// Recursively calling subsetSum
subsetSum( i + 1, curr + c[i]);
subsetSum(i + 1, curr);
}
// Function to generate the subsets
function subsetGen(arr, i, n, ans)
{
// Base-case
if (i == n) {
// Finding the sum of all the subsets
// of the generated subset
subsetSum(0, ans, 0);
return;
}
// Recursively accepting and rejecting
// the current number
subsetGen(arr, i + 1, n, ans);
c.push(arr[i]);
subsetGen(arr, i + 1, n, ans);
c.pop();
}
// Driver code
var arr = [1, 1 ];
var n = arr.length;
// To store the final ans
var ans = 0;
var c = [];
subsetGen(arr, 0, n, ans);
document.write( ans);
</script>
6
Complejidad de tiempo: O(n * 2 n ), para generar todos los subconjuntos donde n es el tamaño de la array dada
Espacio auxiliar: O(n), para almacenar la respuesta final
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA