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 = 35Input: 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 programint K, N;// it returns sum of all the multiplied Subsetint 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 Kvoid 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 codeint 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 subsetdef 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 Kdef 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 codeif __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 Subsetfunction 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 Kfunction 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 codeconst n = 4;const k = 2;const arr = [1, 2, 3, 4];console.log(sumOfProduct(arr, n, k));// This code is contributed by unstoppablepandu. |
Output
35
Time Complexity: 2n
Auxiliary Space: 2n ( 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] *
dp[i-1][k]
answer[k] =
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 subsetsint 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 codeint 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 subsetsdef 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 codeif __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 subsetsfunction 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 codelet 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
35
Time Complexity: O(n2)
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 subsetsint 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 codeint 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 approachimport 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 subsetsdef 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 codearr = [1, 2, 3, 4]n = len(arr)k = 2print(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 subsetsfunction 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 codelet arr = [1, 2, 3, 4];let n = arr.length;let k = 2;console.log(sumOfProduct(arr, n, k)); |
Output
35
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
