数组所有子集的子集总和|O(N)

本文概述

C ++
Java
Python3
C#

给定一个长度为N的数组arr[]，任务是找出该数组所有子集的子集的总和。
例子：

输入：arr [] = {1, 1}
输出：6
所有可能的子集：
a){}：0该子集的所有可能子集将为{}, 总和= 0
b){1}：1所有可能的子集该子集的{}和{1}, 总和= 0 + 1 = 1
c){1}：1此子集的所有可能子集将是{}和{1}, 总和= 0 + 1 = 1
d){1, 1}：4该子集的所有可能子集将是{}, {1}, {1}和{1, 1}, 总和= 0 +1 + 1 + 2 = 4因此, ans = 0 +1 + 1 + 4 = 6
输入：arr [] = {1, 4, 2, 12}
输出：513

方法:本文将讨论一种具有O(N)时间复杂度的方法来解决给定的问题。
关键是观察元素在所有子集中重复的次数。
让我们把视野放大。已知每个元素在子集的和中出现2^(N - 1)次。现在，让我们进一步放大视图，看看计数如何随子集大小而变化。
对于包含它的每个索引，有N - 1CK - 1个大小为K的子集。
一个元素对大小为K的子集的贡献等于2^(K - 1)乘以它的值。因此，一个元素对所有长度为K的子集的总贡献将等于N - 1CK - 1 * 2^(K - 1)
【数组所有子集的子集总和|O(N)】所有子集之间的总贡献将等于：

N – 1CN – 1 * 2(N – 1)+ N – 1CN – 2 * 2(N – 2 + N – 1CN – 3 * 2(N – 3)+…+ N – 1C0 * 20。

现在, 最终答案中每个元素的贡献是已知的。因此, 将其乘以数组所有元素的总和即可得出所需的答案。
下面是上述方法的实现：
C ++

//C++ implementation of the approach #include < bits/stdc++.h> using namespace std; #define maxN 10//To store factorial values int fact[maxN]; //Function to return ncr int ncr( int n, int r) { return (fact[n] /fact[r]) /fact[n - r]; }//Function to return the required sum int findSum( int * arr, int n) { //Intialising factorial fact[0] = 1; for ( int i = 1; i < n; i++) fact[i] = i * fact[i - 1]; //Multiplier int mul = 0; //Finding the value of multipler //according to the formula for ( int i = 0; i < = n - 1; i++) mul += ( int ) pow (2, i) * ncr(n - 1, i); //To store the final answer int ans = 0; //Calculate the final answer for ( int i = 0; i < n; i++) ans += mul * arr[i]; return ans; }//Driver code int main() { int arr[] = { 1, 1 }; int n = sizeof (arr) /sizeof ( int ); cout < < findSum(arr, n); return 0; }

Java

//Java implementation of the approach class GFG { static int maxN = 10 ; //To store factorial values static int []fact = new int [maxN]; //Function to return ncr static int ncr( int n, int r) { return (fact[n] /fact[r]) /fact[n - r]; }//Function to return the required sum static int findSum( int [] arr, int n) { //Intialising factorial fact[ 0 ] = 1 ; for ( int i = 1 ; i < n; i++) fact[i] = i * fact[i - 1 ]; //Multiplier int mul = 0 ; //Finding the value of multipler //according to the formula for ( int i = 0 ; i < = n - 1 ; i++) mul += ( int )Math.pow( 2 , i) * ncr(n - 1 , i); //To store the final answer int ans = 0 ; //Calculate the final answer for ( int i = 0 ; i < n; i++) ans += mul * arr[i]; return ans; }//Driver code public static void main(String []args) { int arr[] = { 1 , 1 }; int n = arr.length; System.out.println(findSum(arr, n)); } }//This code is contributed by Rajput-Ji

Python3

# Python3 implementation of the approach maxN = 10# To store factorial values fact = [ 0 ] * maxN; # Function to return ncr def ncr(n, r) : return (fact[n] //fact[r]) //fact[n - r]; # Function to return the required sum def findSum(arr, n) : # Intialising factorial fact[ 0 ] = 1 ; for i in range ( 1 , n) : fact[i] = i * fact[i - 1 ]; # Multiplier mul = 0 ; # Finding the value of multipler # according to the formula for i in range (n) : mul + = ( 2 * * i) * ncr(n - 1 , i); # To store the final answer ans = 0 ; # Calculate the final answer for i in range (n) : ans + = mul * arr[i]; return ans; # Driver code if __name__ = = "__main__" : arr = [ 1 , 1 ]; n = len (arr); print (findSum(arr, n)); # This code is contributed by AnkitRai01

//C# implementation of the approach using System; class GFG { static int maxN = 10; //To store factorial values static int []fact = new int [maxN]; //Function to return ncr static int ncr( int n, int r) { return (fact[n] /fact[r]) /fact[n - r]; }//Function to return the required sum static int findSum( int [] arr, int n) { //Intialising factorial fact[0] = 1; for ( int i = 1; i < n; i++) fact[i] = i * fact[i - 1]; //Multiplier int mul = 0; //Finding the value of multipler //according to the formula for ( int i = 0; i < = n - 1; i++) mul += ( int )Math.Pow(2, i) * ncr(n - 1, i); //To store the final answer int ans = 0; //Calculate the final answer for ( int i = 0; i < n; i++) ans += mul * arr[i]; return ans; }//Driver code public static void Main(String []args) { int []arr = { 1, 1 }; int n = arr.Length; Console.WriteLine(findSum(arr, n)); } }//This code is contributed by 29AjayKumar

输出如下：