Sum of products of all possible K size subsets of the given array | C ++ implementation of the approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int sumOfProduct ( int arr [ ] , int n , int k ) { int dp [ n + 1 ] [ n + 1 ] = { 0 } ; int cur_sum = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { dp [ 1 ] [ i ] = arr [ i - 1 ] ; cur_sum += arr [ i - 1 ] ; } for ( int i = 2 ; i <= k ; i ++ ) { int temp_sum = 0 ; for ( int j = 1 ; j <= n ; j ++ ) { cur_sum -= dp [ i - 1 ] [ j ] ; dp [ i ] [ j ] = arr [ j - 1 ] * cur_sum ; temp_sum += dp [ i ] [ j ] ; } cur_sum = temp_sum ; } return cur_sum ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 } ; int n = sizeof ( arr ) / sizeof ( int ) ; int k = 2 ; cout << sumOfProduct ( arr , n , k ) ; return 0 ; }