Sum of products of all possible K size subsets of the given array | Function to return the sum of products of all the possible k size subsets ; Initialising all the values to 0 ; To store the answer for current value of k ; For k = 1 , the answer will simply be the sum of all the elements ; Filling the table in bottom up manner ; To store the elements of the current row so that we will be able to use this sum for subsequent values of k ; We will subtract previously computed value so as to get the sum of elements from j + 1 to n in the ( i - 1 ) th row ; Driver code
def sumOfProduct ( arr , n , k ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( n + 1 ) ] for y in range ( n + 1 ) ] NEW_LINE cur_sum = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT dp [ 1 ] [ i ] = arr [ i - 1 ] NEW_LINE cur_sum += arr [ i - 1 ] NEW_LINE DEDENT for i in range ( 2 , k + 1 ) : NEW_LINE INDENT temp_sum = 0 NEW_LINE for j in range ( 1 , n + 1 ) : NEW_LINE INDENT cur_sum -= dp [ i - 1 ] [ j ] NEW_LINE dp [ i ] [ j ] = arr [ j - 1 ] * cur_sum NEW_LINE temp_sum += dp [ i ] [ j ] NEW_LINE DEDENT cur_sum = temp_sum NEW_LINE DEDENT return cur_sum NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE k = 2 NEW_LINE print ( sumOfProduct ( arr , n , k ) ) NEW_LINE DEDENT