Sum of subsets of all the subsets of an array | O ( N ) | Python3 implementation of the approach ; To store factorial values ; Function to return ncr ; Function to return the required sum ; Initialising factorial ; Multiplier ; Finding the value of multipler according to the formula ; To store the final answer ; Calculate the final answer ; Driver code
maxN = 10 NEW_LINE fact = [ 0 ] * maxN ; NEW_LINE def ncr ( n , r ) : NEW_LINE INDENT return ( fact [ n ] // fact [ r ] ) // fact [ n - r ] ; NEW_LINE DEDENT def findSum ( arr , n ) : NEW_LINE INDENT fact [ 0 ] = 1 ; NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT fact [ i ] = i * fact [ i - 1 ] ; NEW_LINE DEDENT mul = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT mul += ( 2 ** i ) * ncr ( n - 1 , i ) ; NEW_LINE DEDENT ans = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT ans += mul * arr [ i ] ; NEW_LINE DEDENT return ans ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 1 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE print ( findSum ( arr , n ) ) ; NEW_LINE DEDENT