Sum of products of all possible K size subsets of the given array

0 0 18 minutes read

Given an array arr[] of N non-negative integers and an integer 1 ? K ? N. The task is to find the sum of the products of all possible subsets of arr[] of size K.

Examples:

Input: arr[] = {1, 2, 3, 4}, K = 2
Output: 35
(1 * 2) + (1 * 3) + (1 * 4) + (2 * 3) + (2 * 4)
+ (3 * 4) = 2 + 3 + 4 + 6 + 8 + 12 = 35

Input: arr[] = {1, 2, 3, 4}, K = 3
Output: 50

Naive approach: Generate all possible subsets of size K and find the resultant product of each subset. Then sum the product obtained for each subset. The time complexity of this solution would be exponential.

C++

// Program  find the sum of the products of all possible
// subsets of arr[] of size K. 
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
// using these variable , to avoid many parameters in a
// recursive function , which will reduce the speed of
// the program
int K, N;
 
// it returns sum of all the multiplied Subset
int getSum(vector<vector<int> > res)
{
    long long sum = 0, MOD = 1000000007;
 
    for (vector<int> tempList : res) {
 
        long long tempSum = 1;
 
        for (int val : tempList) {
 
            tempSum = (tempSum * val) % MOD;
        }
 
        sum = sum + tempSum;
    }
    // we are doing % operation  , so that our result
    // should not get overflow
    return sum % MOD;
}
 
// Generate all Subarray with size K
void createAllPossibleSubset(int arr[],
                             vector<vector<int> >& res,
                             vector<int>& temp, int index)
{
    /*
      when we get the required size subset , we
      add into the result list and return
    */
    if (temp.size() == K) {
        res.push_back(temp);
        return;
    }
 
    // otherwise we add current element ,
    // and move forward to add next element in our
    // subset
    for (int i = index; i < N; i++) {
        temp.push_back(arr[i]);
 
        createAllPossibleSubset(arr, res, temp, i + 1);
 
        // removing the last element , for backtracking
        temp.pop_back();
    }
}
 
 
int sumOfProduct(int arr[], int n, int k)
{
    K = k;
    N = n;
 
    // result store all the subset of size K
    vector<vector<int> > res;
    vector<int> temp;
 
    createAllPossibleSubset(arr, res, temp, 0);
 
    return getSum(res);
}
 
 
// Driver code
int main()
{
    int n = 4, k = 2;
    int arr[] = { 1, 2, 3, 4 };
    cout << sumOfProduct(arr, n, k);
    return 0;
}
// This code is contributed by Pradeep Mondal P

Java

// Program  find the sum of the products of all possible
// subsets of arr[] of size K. 
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // storing the k value , so that it can be easily
    // accessed
    static int K;
 
    public static int sumOfProduct(int arr[], int n, int k)
    {
        K = k;
 
        // result store all the subset of size K
        ArrayList<ArrayList<Integer> > res
            = new ArrayList<>();
 
        createAllPossibleSubset(arr, res, new ArrayList<>(),
                                0);
 
        return getSum(res);
    }
 
    // Generate all Subarray with size K
    static void createAllPossibleSubset(
        int arr[], ArrayList<ArrayList<Integer> > res,
        ArrayList<Integer> temp, int index)
    {
        /*
          when we get the required size subset , we
          add into the result list and return
        */
        if (temp.size() == K) {
            res.add(new ArrayList<>(temp));
            return;
        }
 
        // otherwise we add current element ,
        // and move forward to add next element in our
        // subset
        for (int i = index; i < arr.length; i++) {
            temp.add(arr[i]);
 
            createAllPossibleSubset(arr, res, temp, i + 1);
 
            // removing the last element , for backtracking
            temp.remove(temp.size() - 1);
        }
    }
 
    // it returns sum of all the multiplied Subset
    private static int
    getSum(ArrayList<ArrayList<Integer> > res)
    {
 
        int sum = 0, MOD = 1000000007;
        for (ArrayList<Integer> tempList : res) {
           
            long tempSum = 1;
            for (int val : tempList) {
               
                tempSum *= val % MOD;
            }
 
            sum += tempSum;
        }
        // we are doing % operation  , so that our result
        // should not get overflow
        return sum % MOD;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 4, k = 2;
        int arr[] = { 1, 2, 3, 4 };
        System.out.println(sumOfProduct(arr, n, k));
    }
}
// This code is Contributed by Pradeep Mondal P

Python3

from typing import List, Tuple
 
# function to get the sum of all the multiplied subset
def getSum(res: List[List[int]]) -> int:
    sum = 0
    MOD = 1000000007
    for tempList in res:
        tempSum = 1
        for val in tempList:
            tempSum = (tempSum * val) % MOD
        sum += tempSum
    # we are doing % operation, so that our result should not get overflow
    return sum % MOD
 
# Generate all Subarray with size K
def createAllPossibleSubset(arr: List[int], res: List[List[int]], temp: List[int], index: int, k: int):
    """
    when we get the required size subset , we
    add into the result list and return
    """
    if len(temp) == k:
        res.append(temp[:])
        return
    # otherwise we add current element , and move forward to add next element in our subset
    for i in range(index, len(arr)):
        temp.append(arr[i])
        createAllPossibleSubset(arr, res, temp, i + 1, k)
        # removing the last element , for backtracking
        temp.pop()
 
def sumOfProduct(arr: List[int], k: int) -> int:
    res = []
    temp = []
    createAllPossibleSubset(arr, res, temp, 0, k)
    return getSum(res)
 
# Driver code
if __name__ == "__main__":
    arr = [1, 2, 3, 4]
    k = 2
    print(sumOfProduct(arr, k))
 
    # This code is contributed by pradeepkumarppk2003

C#

// Program  find the sum of the products of all possible
// subsets of []arr of size K. 
using System;
using System.Collections.Generic;
 
public class GFG {
 
  // storing the k value , so that it can be easily
  // accessed
  static int K;
 
  public static long sumOfProduct(int []arr, int n, int k)
  {
    K = k;
 
    // result store all the subset of size K
    List<List<int> > res = new List<List<int>>();
 
    createAllPossibleSubset(arr, res, new List<int>(),
                            0);
 
    return getSum(res);
  }
 
  // Generate all Subarray with size K
  static void createAllPossibleSubset(
    int []arr, List<List<int> > res,
    List<int> temp, int index)
  {
    /*
          when we get the required size subset , we
          add into the result list and return
        */
    if (temp.Count == K) {
      res.Add(new List<int>(temp));
      return;
    }
 
    // otherwise we add current element ,
    // and move forward to add next element in our
    // subset
    for (int i = index; i < arr.Length; i++) {
      temp.Add(arr[i]);
 
      createAllPossibleSubset(arr, res, temp, i + 1);
 
      // removing the last element , for backtracking
      temp.RemoveAt(temp.Count - 1);
    }
  }
 
  // it returns sum of all the multiplied Subset
  private static long
    getSum(List<List<int> > res)
  {
 
    long sum = 0, MOD = 1000000007;
    foreach (List<int> tempList in res) {
 
      long tempSum = 1;
      foreach (int val in tempList) {
 
        tempSum *= val % MOD;
      }
 
      sum += tempSum;
    }
    // we are doing % operation  , so that our result
    // should not get overflow
    return sum % MOD;
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    int n = 4, k = 2;
    int []arr = { 1, 2, 3, 4 };
    Console.WriteLine(sumOfProduct(arr, n, k));
  }
}
 
// This code is contributed by 29AjayKumar

Javascript

// JavaScript Program  find the sum of the products of all possible
// subsets of arr[] of size K. 
 
// it returns sum of all the multiplied Subset
function getSum(res) {
  let sum = 0;
  const MOD = 1000000007;
 
  for (let tempList of res) {
    let tempSum = 1;
 
    for (let val of tempList) {
      tempSum = (tempSum * val) % MOD;
    }
 
    sum = sum + tempSum;
  }
  // we are doing % operation , so that our result
  // should not get overflow
  return sum % MOD;
}
 
// Generate all Subarray with size K
function createAllPossibleSubset(arr, res, temp, index) {
  /*
    when we get the required size subset , we
    add into the result list and return
  */
  if (temp.length === K) {
    res.push(temp);
    return;
  }
 
  // otherwise we add current element ,
  // and move forward to add next element in our
  // subset
  for (let i = index; i < N; i++) {
    temp.push(arr[i]);
 
    createAllPossibleSubset(arr, res, temp, i + 1);
 
    // removing the last element , for backtracking
    temp.pop();
  }
}
 
function sumOfProduct(arr, n, k) {
  K = k;
  N = n;
 
  // result store all the subset of size K
  let res = [];
  let temp = [];
 
  createAllPossibleSubset(arr, res, temp, 0);
 
  return getSum(res);
}
 
// Driver code
const n = 4;
const k = 2;
 
const arr = [1, 2, 3, 4];
console.log(sumOfProduct(arr, n, k));
 
// This code is contributed by unstoppablepandu.

Output

Time Complexity: 2ⁿ
Auxiliary Space: 2ⁿ ( n is the array size )

Efficient approach: Take the example of an array a[] = {1, 2, 3} and K = 3. Then,

k = 1, answer = 1 + 2 + 3 = 6
k = 2, answer = 1 * (2 + 3) + 2 * 3 + 0 = 11
k = 3, answer = 1 * (2 * 3 + 0) + 0 + 0 = 6

In the example, if the contribution of 1 is needed to be obtained in the answer for K = 2 then the sum of all elements after the index of element 1 is required in the previously computed values for K = 1. It can be seen that the sum of elements 2 and 3 is required. Thus, for any K, the answer obtained for K – 1 is required.

So, bottom-up dynamic programming approach can be used to solve this problem. Create a table dp[][] and fill it in bottom up manner where dp[i][j] will store the contribution of an element arr[j – 1] to the answer for K = i. Hence, the recurrence relation will be,

dp[i][j] = arr[j-1] * $\sum_{k=j+1}^{n}$
dp[i-1][k]answer[k] = $\sum_{i=1}^{n}$
dp[k][i]

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the sum of products of
// all the possible k size subsets
int sumOfProduct(int arr[], int n, int k)
{
    // Initialising all the values to 0
    int dp[k + 1][n + 1] = { 0 };
 
    // To store the answer for
    // current value of k
    int cur_sum = 0;
 
    // For k = 1, the answer will simply
    // be the sum of all the elements
    for (int i = 1; i <= n; i++) {
        dp[1][i] = arr[i - 1];
        cur_sum += arr[i - 1];
    }
 
    // Filling the table in bottom up manner
    for (int i = 2; i <= k; i++) {
 
        // To store the elements of the current
        // row so that we will be able to use this sum
        // for subsequent values of k
        int temp_sum = 0;
 
        for (int j = 1; j <= n; j++) {
 
            // 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
            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;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int n = sizeof(arr) / sizeof(int);
    int k = 2;
 
    cout << sumOfProduct(arr, n, k);
 
    return 0;
}

Java

// Java implementation of the approach 
import java.util.*; 
 
class GFG{
 
// Function to return the sum of products of 
// all the possible k size subsets 
static int sumOfProduct(int arr[], int n, 
                        int k) 
{ 
    int dp[][] = new int[n + 1][n + 1];
     
    // Initialising all the values to 0 
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            dp[i][j] = 0;
 
    // To store the answer for 
    // current value of k 
    int cur_sum = 0; 
 
    // For k = 1, the answer will simply 
    // be the sum of all the elements 
    for(int i = 1; i <= n; i++) 
    { 
        dp[1][i] = arr[i - 1]; 
        cur_sum += arr[i - 1]; 
    } 
 
    // Filling the table in bottom
    // up manner 
    for(int i = 2; i <= k; i++) 
    { 
         
        // To store the elements of the 
        // current row so that we will
        // be able to use this sum 
        // for subsequent values of k 
        int temp_sum = 0; 
 
        for(int j = 1; j <= n; j++)
        { 
             
            // 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 
            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; 
} 
 
// Driver code 
public static void main(String[] args) 
{ 
    int arr[] = { 1, 2, 3, 4 }; 
    int n = arr.length;
    int k = 2; 
 
    System.out.print(sumOfProduct(arr, n, k));  
} 
}
 
// This code is contributed by Stream_Cipher

Python3

# Python3 implementation of the approach
  
# Function to return the sum of products of
# all the possible k size subsets
def sumOfProduct(arr, n, k):
     
    # Initialising all the values to 0
    dp = [ [ 0 for x in range(n + 1)] for y in range(n + 1)]
     
    # To store the answer for
    # current value of k
    cur_sum = 0
     
    # For k = 1, the answer will simply
    # be the sum of all the elements
    for i in range(1, n + 1):
        dp[1][i] = arr[i - 1]
        cur_sum += arr[i - 1]
  
    # Filling the table in bottom up manner
    for i in range(2 , k + 1):
  
        # To store the elements of the current
        # row so that we will be able to use this sum
        # for subsequent values of k
        temp_sum = 0
  
        for j in range( 1,  n + 1):
  
            # 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
            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
  
# Driver code
if __name__ == "__main__":
     
    arr = [ 1, 2, 3, 4 ]
    n = len(arr)
    k = 2
    print(sumOfProduct(arr, n, k))
 
# This code is contributed by chitranayal

C#

// C# implementation of the approach 
using System.Collections.Generic; 
using System; 
 
class GFG{
 
// Function to return the sum of products of 
// all the possible k size subsets 
static int sumOfProduct(int []arr, int n, int k) 
{ 
    int [,]dp = new int[n + 1, n + 1];
     
    // Initialising all the values to 0 
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            dp[i, j] = 0;
 
    // To store the answer for 
    // current value of k 
    int cur_sum = 0; 
 
    // For k = 1, the answer will simply 
    // be the sum of all the elements 
    for(int i = 1; i <= n; i++)
    { 
        dp[1, i] = arr[i - 1]; 
        cur_sum += arr[i - 1]; 
    } 
 
    // Filling the table in bottom up manner 
    for(int i = 2; i <= k; i++)
    { 
         
        // To store the elements of the
        // current row so that we will
        // be able to use this sum 
        // for subsequent values of k 
        int temp_sum = 0; 
 
        for(int j = 1; j <= n; j++)
        { 
             
            // 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 
            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; 
} 
 
// Driver code 
public static void Main() 
{ 
    int []arr = { 1, 2, 3, 4 }; 
    int n = arr.Length;
    int k = 2; 
 
    Console.WriteLine(sumOfProduct(arr, n, k));  
} 
}
 
// This code is contributed by Stream_Cipher

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to return the sum of products of
// all the possible k size subsets
function sumOfProduct(arr, n, k)
{
    let dp = new Array(n + 1);
     
    // Initialising all the values to 0
    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;
        }
    }
     
    // To store the answer for
    // current value of k
    let cur_sum = 0;
  
    // For k = 1, the answer will simply
    // be the sum of all the elements
    for(let i = 1; i <= n; i++)
    {
        dp[1][i] = arr[i - 1];
        cur_sum += arr[i - 1];
    }
  
    // Filling the table in bottom
    // up manner
    for(let i = 2; i <= k; i++)
    {
          
        // To store the elements of the
        // current row so that we will
        // be able to use this sum
        // for subsequent values of k
        let temp_sum = 0;
  
        for(let j = 1; j <= n; j++)
        {
              
            // 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
            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;
}
 
// Driver code
let arr = [ 1, 2, 3, 4 ];
let n = arr.length;
let k = 2;
 
document.write(sumOfProduct(arr, n, k)); 
 
// This code is contributed by rag2127
 
</script>

Output

Time Complexity: O(n²)
Auxiliary Space: O(k*n)

Efficient approach : Space Optimization

to optimize the space complexity of previous approach we using a 1D array instead of a 2D array to store the values of the DP table. Since we only need the values of the previous row to compute the values of the current row, we can use a single array to store these values and update it as we iterate over the rows

Implementation Steps:

Initialize an array dp of size n+1 to store the computed values.
Initialize cur_sum variable to 0.
Fill the first row of the dp table with the values from the input array arr.
Compute the sum of all elements in arr and store it in cur_sum.
For each value of i from 2 to k, perform the following:
a. Set temp_sum to 0.
b. For each value of j from 1 to n, perform the following:
i. Subtract the previously computed value from dp[j] to get the sum of elements from j + 1 to n in the (i – 1)th row.
ii. Multiply the value of arr[j-1] with the current sum computed in step (i) and store it in dp[j].
iii. Add the value of dp[j] to temp_sum.
c. Update the value of cur_sum with the value of temp_sum.
Return the value of cur_sum.

Implementation:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the sum of products of
// all the possible k size subsets
int sumOfProduct(int arr[], int n, int k)
{
    // Initialising all the values to 0
    int dp[n + 1] = { 0 };
 
    // To store the answer for
    // current value of k
    int cur_sum = 0;
 
    // For k = 1, the answer will simply
    // be the sum of all the elements
    for (int i = 1; i <= n; i++) {
        dp[i] = arr[i - 1];
        cur_sum += arr[i - 1];
    }
 
    // Filling the table in bottom up manner
    for (int i = 2; i <= k; i++) {
 
        // To store the elements of the current
        // row so that we will be able to use this sum
        // for subsequent values of k
        int temp_sum = 0;
 
        for (int j = 1; j <= n; j++) {
 
            // 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
            cur_sum -= dp[j];
 
            dp[j] = arr[j - 1] * cur_sum;
            temp_sum += dp[j];
        }
       
          // assigning values for further computation
        cur_sum = temp_sum;
    }
    return cur_sum;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int n = sizeof(arr) / sizeof(int);
    int k = 2;
 
    cout << sumOfProduct(arr, n, k);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG {
  // Function to return the sum of products of
  // all the possible k size subsets
  static int sumOfProduct(int[] arr, int n, int k)
  {
      // Initialising all the values to 0
      int[] dp = new int[n + 1];
 
      // To store the answer for
      // current value of k
      int cur_sum = 0;
 
      // For k = 1, the answer will simply
      // be the sum of all the elements
      for (int i = 1; i <= n; i++) {
          dp[i] = arr[i - 1];
          cur_sum += arr[i - 1];
      }
 
      // Filling the table in bottom up manner
      for (int i = 2; i <= k; i++) {
 
          // To store the elements of the current
          // row so that we will be able to use this sum
          // for subsequent values of k
          int temp_sum = 0;
 
          for (int j = 1; j <= n; j++) {
 
              // 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
              cur_sum -= dp[j];
 
              dp[j] = arr[j - 1] * cur_sum;
              temp_sum += dp[j];
          }
 
          // Assigning values for further computation
          cur_sum = temp_sum;
      }
      return cur_sum;
  }
 
  // Driver code
  public static void main(String[] args)
  {
      int[] arr = { 1, 2, 3, 4 };
      int n = arr.length;
      int k = 2;
 
      System.out.println(sumOfProduct(arr, n, k));
  }
}

Python3

# Function to return the sum of products of
# all the possible k size subsets
def sumOfProduct(arr, n, k):
    # Initialising all the values to 0
    dp = [0] * (n + 1)
 
    # To store the answer for
    # current value of k
    cur_sum = 0
 
    # For k = 1, the answer will simply
    # be the sum of all the elements
    for i in range(1, n + 1):
        dp[i] = arr[i - 1]
        cur_sum += arr[i - 1]
 
    # Filling the table in bottom up manner
    for i in range(2, k + 1):
 
        # To store the elements of the current
        # row so that we will be able to use this sum
        # for subsequent values of k
        temp_sum = 0
 
        for j in range(1, n + 1):
 
            # 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
            cur_sum -= dp[j]
 
            dp[j] = arr[j - 1] * cur_sum
            temp_sum += dp[j]
 
        # assigning values for further computation
        cur_sum = temp_sum
 
    return cur_sum
 
# Driver code
arr = [1, 2, 3, 4]
n = len(arr)
k = 2
 
print(sumOfProduct(arr, n, k))

C#

using System;
 
class GFG {
 
    // Function to return the sum of products of
    // all the possible k size subsets
    static int SumOfProduct(int[] arr, int n, int k)
    {
        // Initialising all the values to 0
        int[] dp = new int[n + 1];
 
        // To store the answer for
        // current value of k
        int cur_sum = 0;
 
        // For k = 1, the answer will simply
        // be the sum of all the elements
        for (int i = 1; i <= n; i++) {
            dp[i] = arr[i - 1];
            cur_sum += arr[i - 1];
        }
 
        // Filling the table in bottom up manner
        for (int i = 2; i <= k; i++) {
 
            // To store the elements of the current
            // row so that we will be able to use this sum
            // for subsequent values of k
            int temp_sum = 0;
 
            for (int j = 1; j <= n; j++) {
 
                // 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
                cur_sum -= dp[j];
 
                dp[j] = arr[j - 1] * cur_sum;
                temp_sum += dp[j];
            }
 
            // assigning values for further computation
            cur_sum = temp_sum;
        }
        return cur_sum;
    }
 
    // Driver code
    static void Main(string[] args)
    {
        int[] arr = { 1, 2, 3, 4 };
        int n = arr.Length;
        int k = 2;
 
        Console.WriteLine(SumOfProduct(arr, n, k));
    }
}

Javascript

// Function to return the sum of products of
// all the possible k size subsets
function sumOfProduct(arr, n, k) {
    // Initialising all the values to 0
    let dp = new Array(n + 1).fill(0);
 
    // To store the answer for
    // current value of k
    let cur_sum = 0;
 
    // For k = 1, the answer will simply
    // be the sum of all the elements
    for (let i = 1; i <= n; i++) {
        dp[i] = arr[i - 1];
        cur_sum += arr[i - 1];
    }
 
    // Filling the table in bottom up manner
    for (let i = 2; i <= k; i++) {
        // To store the elements of the current
        // row so that we will be able to use this sum
        // for subsequent values of k
        let temp_sum = 0;
 
        for (let j = 1; j <= n; j++) {
            // 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
            cur_sum -= dp[j];
 
            dp[j] = arr[j - 1] * cur_sum;
            temp_sum += dp[j];
        }
 
        // assigning values for further computation
        cur_sum = temp_sum;
    }
    return cur_sum;
}
 
// Driver code
let arr = [1, 2, 3, 4];
let n = arr.length;
let k = 2;
 
console.log(sumOfProduct(arr, n, k));

Output

Time Complexity: O(N*K)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!