Given an array, arr[] of size N, the task is to find the median of sums of all possible subsets of the given array.
Examples:
Input: arr = {2, 3, 3}
Output: 5
Explanation:
Non-Empty Subsets of the given array are: { {2}, {3}, {3}, {2, 3}, {2, 3}, {3, 3}, {2, 3, 3} }.
Possible sum of each subset are:
{ {2}, {3}, {3}, {5}, {5}, {6}, {8} }
Therefore, the median of all possible sum of each subset is 5.Input: arr = {1, 2, 1}
Output: 2
Naive Approach: The simplest approach to solve this problem is to generate all possible subsets of the given array and find the sum of elements of each subset. Finally, print the median of all possible subset-sum.
Time Complexity: O(N * 2N)
Auxiliary Space: O(N * 2N)
Efficient Approach: To optimize the above approach the idea is to use Dynamic programming. Following are the relation of Dynamic programming states and the base cases:
Relation between DP states:
if j ? arr[i] then dp[i][j] = dp[i – 1][j] + dp[i – 1][j – arr[i]]
Otherwise, dp[i][j] = dp[i – 1][j]
where dp[i][j] denotes total number of ways to obtain the sum j either by selecting the ith element or not selecting the ith element.Base case: dp[i][0] = 1
Follow the steps below to solve the problem:
- Initialize a 2D array, say DP[][] to store the above mentioned DP states.
- Fill all the dp[][] state in a bottom-up manner using the above-mentioned relation between the DP states.
- Initialize an array, say sumSub[] to store all possible sum of each subset.
- Traverse the dp[][] array and store sums of all possible subsets in the array sumSub[].
- Sort the sumSub[] array.
- Finally, print the middle element of sumSub[] array.
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the median of all // possible subsets by given operations int findMedianOfsubSum( int arr[], int N) { // Stores sum of elements // of arr[] int sum=0; // Traverse the array arr[] for ( int i=0; i < N; i++) { // Update sum sum += arr[i]; } // Sort the array sort(arr, arr + N); // DP[i][j]: Stores total number of ways // to form the sum j by either selecting // ith element or not selecting ith item. int dp[N][sum+1]; // Initialize all // the DP states memset (dp, 0, sizeof (dp)); // Base case for ( int i=0; i < N; i++) { // Fill dp[i][0] dp[i][0] = 1; } // Base case dp[0][arr[0]] = 1; // Fill all the DP states based // on the mentioned DP relation for ( int i = 1; i < N; i++) { for ( int j = 1; j <= sum; j++) { // If j is greater than // or equal to arr[i] if (j >= arr[i]) { // Update dp[i][j] dp[i][j] = dp[i-1][j] + dp[i-1][j-arr[i]]; } else { // Update dp[i][j] dp[i][j] = dp[i-1][j]; } } } // Stores all possible // subset sum vector< int > sumSub; // Traverse all possible subset sum for ( int j=1; j <= sum; j++) { // Stores count of subsets // whose sum is j int M = dp[N - 1][j]; // Iterate over the range [1, M] for ( int i = 1; i <= M; i++) { // Insert j into sumSub sumSub.push_back(j); } } // Stores middle element of sumSub int mid = sumSub[sumSub.size() / 2]; return mid; } // Driver Code int main() { int arr[] = { 2, 3, 3 }; int N = sizeof (arr) / sizeof (arr[0]); cout << findMedianOfsubSum(arr, N); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to calculate the median of all // possible subsets by given operations static int findMedianOfsubSum( int arr[], int N) { // Stores sum of elements // of arr[] int sum = 0 ; // Traverse the array arr[] for ( int i = 0 ; i < N; i++) { // Update sum sum += arr[i]; } // Sort the array Arrays.sort(arr); // DP[i][j]: Stores total number of ways // to form the sum j by either selecting // ith element or not selecting ith item. int [][]dp = new int [N][sum + 1 ]; // Initialize all // the DP states for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < sum + 1 ; j++) dp[i][j] = 0 ; } // Base case for ( int i = 0 ; i < N; i++) { // Fill dp[i][0] dp[i][ 0 ] = 1 ; } // Base case dp[ 0 ][arr[ 0 ]] = 1 ; // Fill all the DP states based // on the mentioned DP relation for ( int i = 1 ; i < N; i++) { for ( int j = 1 ; j <= sum; j++) { // If j is greater than // or equal to arr[i] if (j >= arr[i]) { // Update dp[i][j] dp[i][j] = dp[i - 1 ][j] + dp[i - 1 ][j - arr[i]]; } else { // Update dp[i][j] dp[i][j] = dp[i - 1 ][j]; } } } // Stores all possible // subset sum Vector<Integer> sumSub = new Vector<Integer>(); // Traverse all possible subset sum for ( int j = 1 ; j <= sum; j++) { // Stores count of subsets // whose sum is j int M = dp[N - 1 ][j]; // Iterate over the range [1, M] for ( int i = 1 ; i <= M; i++) { // Insert j into sumSub sumSub.add(j); } } // Stores middle element of sumSub int mid = sumSub.get(sumSub.size() / 2 ); return mid; } // Driver Code public static void main(String args[]) { int arr[] = { 2 , 3 , 3 }; int N = arr.length; System.out.print(findMedianOfsubSum(arr, N)); } } // This code is contributed by ipg2016107 |
Python3
# Python3 program to implement # the above approach # Function to calculate the # median of all possible subsets # by given operations def findMedianOfsubSum(arr, N): # Stores sum of elements # of arr[] sum = 0 # Traverse the array arr[] for i in range (N): # Update sum sum + = arr[i] # Sort the array arr.sort(reverse = False ) # DP[i][j]: Stores total number # of ways to form the sum j by # either selecting ith element # or not selecting ith item. dp = [[ 0 for i in range ( sum + 1 )] for j in range (N)] # Base case for i in range (N): # Fill dp[i][0] dp[i][ 0 ] = 1 # Base case dp[ 0 ][arr[ 0 ]] = 1 # Fill all the DP states based # on the mentioned DP relation for i in range ( 1 , N, 1 ): for j in range ( 1 , sum + 1 , 1 ): # If j is greater than # or equal to arr[i] if (j > = arr[i]): # Update dp[i][j] dp[i][j] = (dp[i - 1 ][j] + dp[i - 1 ][j - arr[i]]) else : # Update dp[i][j] dp[i][j] = dp[i - 1 ][j] # Stores all possible # subset sum sumSub = [] # Traverse all possible # subset sum for j in range ( 1 , sum + 1 , 1 ): # Stores count of subsets # whose sum is j M = dp[N - 1 ][j] # Iterate over the # range [1, M] for i in range ( 1 , M + 1 , 1 ): # Insert j into sumSub sumSub.append(j) # Stores middle element # of sumSub mid = sumSub[ len (sumSub) / / 2 ] return mid # Driver Code if __name__ = = '__main__' : arr = [ 2 , 3 , 3 ] N = len (arr) print (findMedianOfsubSum(arr, N)) # This code is contributed by bgangwar59 |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Function to calculate the median of all // possible subsets by given operations static int findMedianOfsubSum( int [] arr, int N) { // Stores sum of elements // of arr[] int sum = 0; // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Update sum sum += arr[i]; } // Sort the array Array.Sort(arr); // DP[i][j]: Stores total number of ways // to form the sum j by either selecting // ith element or not selecting ith item. int [,]dp = new int [N, sum + 1]; // Initialize all // the DP states for ( int i = 0; i < N; i++) { for ( int j = 0; j < sum + 1; j++) dp[i, j] = 0; } // Base case for ( int i = 0; i < N; i++) { // Fill dp[i][0] dp[i, 0] = 1; } // Base case dp[0, arr[0]] = 1; // Fill all the DP states based // on the mentioned DP relation for ( int i = 1; i < N; i++) { for ( int j = 1; j <= sum; j++) { // If j is greater than // or equal to arr[i] if (j >= arr[i]) { // Update dp[i][j] dp[i, j] = dp[i - 1, j] + dp[i - 1, j - arr[i]]; } else { // Update dp[i][j] dp[i, j] = dp[i - 1, j]; } } } // Stores all possible // subset sum List< int > sumSub = new List< int >(); // Traverse all possible subset sum for ( int j = 1; j <= sum; j++) { // Stores count of subsets // whose sum is j int M = dp[N - 1, j]; // Iterate over the range [1, M] for ( int i = 1; i <= M; i++) { // Insert j into sumSub sumSub.Add(j); } } // Stores middle element of sumSub int mid = sumSub[sumSub.Count / 2]; return mid; } // Driver code public static void Main() { int [] arr = { 2, 3, 3 }; int N = arr.Length; Console.Write(findMedianOfsubSum(arr, N)); } } // This code is contributed by sanjoy_62 |
Javascript
<script> // Javascript program to implement // the above approach // Function to calculate the median of all // possible subsets by given operations function findMedianOfsubSum(arr, N) { // Stores sum of elements // of arr[] var sum = 0; // Traverse the array arr[] for ( var i = 0; i < N; i++) { // Update sum sum += arr[i]; } // Sort the array arr.sort((a, b) => a - b) // DP[i][j]: Stores total number of ways // to form the sum j by either selecting // ith element or not selecting ith item. var dp = Array.from( Array(N), () => Array(sum + 1).fill(0)); // Base case for ( var i = 0; i < N; i++) { // Fill dp[i][0] dp[i][0] = 1; } // Base case dp[0][arr[0]] = 1; // Fill all the DP states based // on the mentioned DP relation for ( var i = 1; i < N; i++) { for ( var j = 1; j <= sum; j++) { // If j is greater than // or equal to arr[i] if (j >= arr[i]) { // Update dp[i][j] dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i]]; } else { // Update dp[i][j] dp[i][j] = dp[i - 1][j]; } } } // Stores all possible // subset sum var sumSub = []; // Traverse all possible subset sum for ( var j = 1; j <= sum; j++) { // Stores count of subsets // whose sum is j var M = dp[N - 1][j]; // Iterate over the range [1, M] for ( var i = 1; i <= M; i++) { // Insert j into sumSub sumSub.push(j); } } // Stores middle element of sumSub var mid = sumSub[parseInt(sumSub.length / 2)]; return mid; } // Driver Code var arr = [ 2, 3, 3 ]; var N = arr.length document.write(findMedianOfsubSum(arr, N)); // This code is contributed by importantly </script> |
5
Time Complexity: O(N*Sum), where N is the size of the array and Sum is the sum of all the elements in the array.
Auxiliary Space: O(N*Sum). We use a 2-dimensional array of size N*Sum to store the intermediate results.
Efficient Approach : using array instead of 2d matrix to optimize space complexity
In previous code we can se that dp[i][j] is dependent upon dp[i-1][j-1] or dp[i][j-1] so we can assume that dp[i-1] is previous row and dp[i] is current row.
Implementations Steps :
- Create two vectors prev and curr each of size sum+1, where sum is the sum of all elements of arr. These vectors are used to store the total number of ways to form the sum j using the elements of arr.
- Initialize them with base cases.
- Now In previous code change dp[i] to curr and change dp[i-1] to prev to keep track only of the two main rows.
- After every iteration update previous row to current row to iterate further.
Implementation :
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the median of all // possible subsets by given operations int findMedianOfsubSum( int arr[], int N) { // Stores sum of elements // of arr[] int sum=0; // Traverse the array arr[] for ( int i=0; i < N; i++) { // Update sum sum += arr[i]; } // Sort the array sort(arr, arr + N); // vectors Stores total number of ways // to form the sum j vector< int >prev(sum+1 , 0); vector< int >curr(sum+1 , 0); // Base case for ( int i=0; i < N; i++) { // Fill prev row prev[0] = 1; } // Base case prev[arr[0]] = 1; curr[arr[0]] = 1; // Fill all the current and previous row states for ( int i = 1; i < N; i++) { for ( int j = 1; j <= sum; j++) { // If j is greater than // or equal to arr[i] if (j >= arr[i]) { // Update currect row curr[j] = prev[j] + prev[j-arr[i]]; } else { // Update current row curr[j] = prev[j]; } } prev = curr; } // Stores all possible // subset sum vector< int > sumSub; // Traverse all possible subset sum for ( int j=1; j <= sum; j++) { // Stores count of subsets // whose sum is j int M = curr[j]; // Iterate over the range [1, M] for ( int i = 1; i <= M; i++) { // Insert j into sumSub sumSub.push_back(j); } } // Stores middle element of sumSub int mid = sumSub[sumSub.size() / 2]; return mid; } // Driver Code int main() { int arr[] = { 2, 3, 3 }; int N = sizeof (arr) / sizeof (arr[0]); cout << findMedianOfsubSum(arr, N); return 0; } // this code is contributed by bhardwajji |
Java
import java.util.Arrays; import java.util.ArrayList; public class MedianOfSubSum { // Function to calculate the median of all // possible subsets by given operations static int findMedianOfSubSum( int [] arr, int N) { // Stores sum of elements of arr[] int sum = 0 ; // Traverse the array arr[] for ( int i = 0 ; i < N; i++) { // Update sum sum += arr[i]; } // Sort the array Arrays.sort(arr); // Vector to store total number of ways // to form the sum j int [] prev = new int [sum + 1 ]; int [] curr = new int [sum + 1 ]; // Base case for ( int i = 0 ; i < N; i++) { // Fill prev row prev[ 0 ] = 1 ; } // Base case prev[arr[ 0 ]] = 1 ; curr[arr[ 0 ]] = 1 ; // Fill all the current and previous row states for ( int i = 1 ; i < N; i++) { for ( int j = 1 ; j <= sum; j++) { // If j is greater than or equal to arr[i] if (j >= arr[i]) { // Update current row curr[j] = prev[j] + prev[j - arr[i]]; } else { // Update current row curr[j] = prev[j]; } } prev = curr.clone(); } // List to store all possible subset sums ArrayList<Integer> sumSub = new ArrayList<>(); // Traverse all possible subset sums for ( int j = 1 ; j <= sum; j++) { // Count of subsets whose sum is j int M = curr[j]; // Iterate over the range [1, M] for ( int i = 1 ; i <= M; i++) { // Insert j into sumSub sumSub.add(j); } } // Middle element of sumSub int mid = sumSub.get(sumSub.size() / 2 ); return mid; } // Driver Code public static void main(String[] args) { int [] arr = { 2 , 3 , 3 }; int N = arr.length; System.out.println(findMedianOfSubSum(arr, N)); } } |
Python3
import math # Function to calculate the median of all # possible subsets by given operations def findMedianOfsubSum(arr, N): # Stores sum of elements of arr[] sum = 0 # Traverse the array arr[] for i in range (N): # Update sum sum + = arr[i] # Sort the array arr.sort() # vectors Stores total number of ways to form the sum j prev = [ 0 ] * ( sum + 1 ) curr = [ 0 ] * ( sum + 1 ) # Base case for i in range (N): # Fill prev row prev[ 0 ] = 1 # Base case prev[arr[ 0 ]] = 1 curr[arr[ 0 ]] = 1 # Fill all the current and previous row states for i in range ( 1 , N): for j in range ( 1 , sum + 1 ): # If j is greater than or equal to arr[i] if j > = arr[i]: # Update currect row curr[j] = prev[j] + prev[j - arr[i]] else : # Update current row curr[j] = prev[j] prev = curr[:] # Stores all possible subset sum sumSub = [] # Traverse all possible subset sum for j in range ( 1 , sum + 1 ): # Stores count of subsets whose sum is j M = curr[j] # Iterate over the range [1, M] for i in range ( 1 , M + 1 ): # Insert j into sumSub sumSub.append(j) # Stores middle element of sumSub mid = sumSub[math.floor( len (sumSub) / 2 )] return mid # Driver Code arr = [ 2 , 3 , 3 ] N = len (arr) print (findMedianOfsubSum(arr, N)) |
C#
using System; using System.Collections.Generic; public class MedianOfSubSum { // Function to calculate the median of all // possible subsets by given operations static int findMedianOfSubSum( int [] arr, int N) { // Stores sum of elements of arr[] int sum = 0; // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Update sum sum += arr[i]; } // Sort the array Array.Sort(arr); // Array to store total number of ways // to form the sum j int [] prev = new int [sum + 1]; int [] curr = new int [sum + 1]; // Base case for ( int i = 0; i < N; i++) { // Fill prev row prev[0] = 1; } // Base case prev[arr[0]] = 1; curr[arr[0]] = 1; // Fill all the current and previous row states for ( int i = 1; i < N; i++) { for ( int j = 1; j <= sum; j++) { // If j is greater than or equal to arr[i] if (j >= arr[i]) { // Update current row curr[j] = prev[j] + prev[j - arr[i]]; } else { // Update current row curr[j] = prev[j]; } } prev = ( int [])curr.Clone(); } // List to store all possible subset sums List< int > sumSub = new List< int >(); // Traverse all possible subset sums for ( int j = 1; j <= sum; j++) { // Count of subsets whose sum is j int M = curr[j]; // Iterate over the range [1, M] for ( int i = 1; i <= M; i++) { // Insert j into sumSub sumSub.Add(j); } } // Middle element of sumSub int mid = sumSub[sumSub.Count / 2]; return mid; } // Driver Code public static void Main( string [] args) { int [] arr = { 2, 3, 3 }; int N = arr.Length; Console.WriteLine(findMedianOfSubSum(arr, N)); } } |
Javascript
// Function to calculate the median of all // possible subsets by given operations function findMedianOfsubSum(arr, N) { // Stores sum of elements // of arr[] let sum = 0; // Traverse the array arr[] for (let i = 0; i < N; i++) { // Update sum sum += arr[i]; } // Sort the array arr.sort((a, b) => a - b); // vectors Stores total number of ways // to form the sum j let prev = new Array(sum + 1).fill(0); let curr = new Array(sum + 1).fill(0); // Base case for (let i = 0; i < N; i++) { // Fill prev row prev[0] = 1; } // Base case prev[arr[0]] = 1; curr[arr[0]] = 1; // Fill all the current and previous row states for (let i = 1; i < N; i++) { for (let j = 1; j <= sum; j++) { // If j is greater than or equal to arr[i] if (j >= arr[i]) { // Update current row curr[j] = prev[j] + prev[j - arr[i]]; } else { // Update current row curr[j] = prev[j]; } } prev = [...curr]; } // Stores all possible subset sum let sumSub = []; // Traverse all possible subset sum for (let j = 1; j <= sum; j++) { // Stores count of subsets whose sum is j let M = curr[j]; // Iterate over the range [1, M] for (let i = 1; i <= M; i++) { // Insert j into sumSub sumSub.push(j); } } // Stores middle element of sumSub let mid = sumSub[Math.floor(sumSub.length / 2)]; return mid; } // Driver Code let arr = [2, 3, 3]; let N = arr.length; console.log(findMedianOfsubSum(arr, N)); |
5
Time Complexity: O(N*Sum)
Auxiliary Space: O(Sum)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!