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

2021年4月23日17:16:10 发表评论 725 次浏览

## 本文概述

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

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);

int ans = 0;

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);

int ans = 0 ;

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 ;

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);

int ans = 0;

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