Suma de todos los subconjuntos de un tamaño dado (=K)

Dada una array arr[] que consta de N enteros y un entero positivo K , la tarea es encontrar la suma de todos los subconjuntos de tamaño K .

Ejemplos:

Entrada: arr[] = {1, 2, 4, 5}, K = 2
Salida: 36
Explicación:
Los subconjuntos de tamaño K(= 2) son = {1, 2}, {1, 4}, {1, 5}, {2, 4}, {2, 5}, {4, 5}. Ahora, la suma de todos los subconjuntos suma = 3 + 5 + 6 + 6 + 7 + 9 = 36.

Entrada: arr[] = {2, 4, 5, 6, 8}, K=3
Salida: 150

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los subconjuntos posibles de la array dada y encontrar la suma de los elementos de esos subconjuntos cuyo tamaño es K . Después de encontrar la suma de todos los subconjuntos de tamaño K , imprima la suma de todas las sumas obtenidas como resultado.

Complejidad temporal: O(K*2 ^N )
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar observando el hecho de que el número de ocurrencias de cada elemento arr[i] en la serie de suma depende del valor de N y K. 

Encontremos la ocurrencia de un elemento general x en una serie de sumatoria:

• Ocurrencia de x en series de suma de todos los subconjuntos size=k = ^n-1 C _k-1

Por lo tanto, la frecuencia de cada elemento de arr[] es la misma en la ecuación de sumatoria =   ^n-1 C _k-1 . Por lo tanto, la suma de todos los subconjuntos = (Suma de todos los elementos del arreglo) * ^n-1 C _k-1 .

Siga los pasos a continuación para resolver el problema dado:

• Inicialice la variable, diga freq como 0 y calcule ^n-1 C _k-1
• Inicialice la variable, diga suma como 0 para almacenar la suma de todos los elementos de la array .
• Después de realizar los pasos anteriores, imprima el valor de sum*freq como la suma resultante.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sum of all
// sub-sets of size K
void findSumOfAllSubsets(int arr[], int n, int k)
{
 
    // Frequency of each array element
    // in summation equation.
    int factorial_N=1, factorial_d=1, factorial_D=1;
   
    //calculate factorial of n-1
    for(int i=1; i<=n-1; i++)
      factorial_N*=i;
    //calculate factorial of k-1
    for(int i=1; i<=k-1; i++)
      factorial_d*=i;
    //calculate factorial of n-k
    for(int i=1; i<=n-k; i++)
      factorial_D*=i;
   
    int freq = factorial_N/(factorial_d * factorial_D);
 
    // Calculate sum of array.
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
     
    // Sum of all subsets of size k.
    sum = sum * freq;
 
    cout <<"Sum of all subsets of size = "<<k<<" is => "<< sum << endl;
}
 
// Driver Code
int main()
{
 
    int arr[] = { 1, 2, 4, 5 };
    int n = 4, k = 2;
 
    findSumOfAllSubsets(arr, n, k);
 
    return 0;
}

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG
{
   
    // Function to find the sum of all
    // sub-sets of size K
    static void findSumOfAllSubsets(int[] arr, int n, int k)
    {
 
        // Frequency of each array element
        // in summation equation.
        int factorial_N = 1, factorial_d = 1,
            factorial_D = 1;
 
        // calculate factorial of n-1
        for (int i = 1; i <= n - 1; i++)
            factorial_N *= i;
       
        // calculate factorial of k-1
        for (int i = 1; i <= k - 1; i++)
            factorial_d *= i;
       
        // calculate factorial of n-k
        for (int i = 1; i <= n - k; i++)
            factorial_D *= i;
 
        int freq
            = factorial_N / (factorial_d * factorial_D);
 
        // Calculate sum of array.
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += arr[i];
 
        // Sum of all subsets of size k.
        sum = sum * freq;
 
        System.out.println("Sum of all subsets of size = "
                           + k + " is => " + sum);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        int[] arr = { 1, 2, 4, 5 };
        int n = 4, k = 2;
 
        findSumOfAllSubsets(arr, n, k);
    }
}
 
// This code is contributed by maddler.

# Python 3 program for the above approach
 
# Function to find the sum of all
# sub-sets of size K
def findSumOfAllSubsets(arr, n, k):
   
    # Frequency of each array element
    # in summation equation.
    factorial_N = 1
    factorial_d = 1
    factorial_D = 1
  
    # calculate factorial of n-1
    for i in range(1, n, 1):
        factorial_N *= i
         
    # calculate factorial of k-1
    for i in range(1, k, 1):
        factorial_d *= i
         
    # calculate factorial of n-k
    for i in range(1, n - k + 1, 1):
        factorial_D *= i
  
    freq = factorial_N//(factorial_d * factorial_D)
 
    # Calculate sum of array.
    sum = 0
    for i in range(n):
        sum += arr[i]
 
    # Sum of all subsets of size k.
    sum = sum * freq
    print("Sum of all subsets of size = ",k," is =>",sum)
 
# Driver Code
if __name__ == '__main__':
    arr = [1, 2, 4, 5]
    n = 4
    k = 2
 
    findSumOfAllSubsets(arr, n, k)
     
    # This code is contributed by SURENDRA_GANGWAR.

// C# program for the above approach
using System;
class GFG
{
   
    // Function to find the sum of all
    // sub-sets of size K
    static void findSumOfAllSubsets(int[] arr, int n, int k)
    {
 
        // Frequency of each array element
        // in summation equation.
        int factorial_N = 1, factorial_d = 1,
            factorial_D = 1;
 
        // calculate factorial of n-1
        for (int i = 1; i <= n - 1; i++)
            factorial_N *= i;
        // calculate factorial of k-1
        for (int i = 1; i <= k - 1; i++)
            factorial_d *= i;
        // calculate factorial of n-k
        for (int i = 1; i <= n - k; i++)
            factorial_D *= i;
 
        int freq
            = factorial_N / (factorial_d * factorial_D);
 
        // Calculate sum of array.
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += arr[i];
 
        // Sum of all subsets of size k.
        sum = sum * freq;
 
        Console.WriteLine("Sum of all subsets of size = "
                          + k + " is => " + sum);
    }
 
    // Driver Code
    public static void Main()
    {
 
        int[] arr = { 1, 2, 4, 5 };
        int n = 4, k = 2;
 
        findSumOfAllSubsets(arr, n, k);
    }
}
 
// This code is contributed by ukasp.

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to find the sum of all
        // sub-sets of size K
        function findSumOfAllSubsets(arr, n, k) {
 
            // Frequency of each array element
            // in summation equation.
            let factorial_N = 1, factorial_d = 1, factorial_D = 1;
 
            // calculate factorial of n-1
            for (let i = 1; i <= n - 1; i++)
                factorial_N *= i;
                 
            // calculate factorial of k-1
            for (let i = 1; i <= k - 1; i++)
                factorial_d *= i;
                 
            // calculate factorial of n-k
            for (let i = 1; i <= n - k; i++)
                factorial_D *= i;
 
            let freq = factorial_N / (factorial_d * factorial_D);
 
            // Calculate sum of array.
            let sum = 0;
            for (let i = 0; i < n; i++)
                sum += arr[i];
 
            // Sum of all subsets of size k.
            sum = sum * freq;
 
            document.write("Sum of all subsets of size = " + k + " is => " + sum + "<br>");
        }
 
        // Driver Code
        let arr = [1, 2, 4, 5];
        let n = 4, k = 2;
 
        findSumOfAllSubsets(arr, n, k);
 
// This code is contributed by Potta Lokesh
    </script>

36

Complejidad temporal: O(N)
Espacio auxiliar: O(1)