# Sum of all subsets of a given size (=K)

Given an array **arr[]** consisting of **N** integers and a positive integer **K**, the task is to find the sum of all the subsets of size **K**.

**Examples:**

Input:arr[] = {1, 2, 4, 5}, K = 2Output:36Explanation:

The subsets of size K(= 2) are = {1, 2}, {1, 4}, {1, 5}, {2, 4}, {2, 5}, {4, 5}. Now, the sum of all subsets sum = 3 + 5 + 6 + 6 + 7 + 9 = 36.

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

**Naive Approach:** The simplest approach to solve the given problem is to generate all possible subsets of the given array and find the sum of elements of those subsets whose size is **K**. After finding the sum of all **K sized subsets**, print the sum of all the sums obtained as the result.

**Time Complexity:** O(K*2^{N})**Auxiliary Space:** O(1)

**Efficient Approach:** The above approach can also be optimized by observing the fact that the number of occurrences of each element **arr[i]** in the summation series depends on value of N and K.

Let’s find the occurrence of a general element x in summation series:

- Occurence of x in summation series of all size=k subsets =
^{n-1}C_{k-1}

Therefore, the frequency of each element of arr[] is same in the summation equation = ^{n-1}C_{k-1}. Hence, the sum of all the subsets = (Sum of all elements of the array) * ^{n-1}C_{k-1}.

Follow the steps below to solve the given problem:

- Initialize the variable, say
**freq**as 0 and calculate^{n-1}C_{k-1} - Initialize the variable, say
**sum**as**0**to store the sum of all the array elements. - After performing the above steps, print the value of
**sum*freq**as the resultant sum.

Below is the implementation of the above approach:

## C++

`// 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;` `}` |

## Java

`/*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.` |

## Python3

`# 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#

`// 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.` |

## Javascript

`<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>` |

**Output**

36

**Time Complexity:** O(N)**Auxiliary Space:** O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.