数组所有子集的子集总和|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)

所有子集之间的总贡献将等于：

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#

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

输出如下：

6

---