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
function sumOfProduct ( arr , n , k ) { let dp = new Array ( n + 1 ) ; for ( let i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( n + 1 ) ; for ( let j = 0 ; j < dp [ i ] . length ; j ++ ) { dp [ i ] [ j ] = 0 ; } } let cur_sum = 0 ; for ( let i = 1 ; i <= n ; i ++ ) { dp [ 1 ] [ i ] = arr [ i - 1 ] ; cur_sum += arr [ i - 1 ] ; } for ( let i = 2 ; i <= k ; i ++ ) { let temp_sum = 0 ; for ( let 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 ; } let arr = [ 1 , 2 , 3 , 4 ] ; let n = arr . length ; let k = 2 ; document . write ( sumOfProduct ( arr , n , k ) ) ;