Given an array arr[] consisting of N positive integers and a positive integer K, the task is to find the minimum difference between the sum of elements present in two subsets of size K, such that each array element can occur in at most 1 subset.
Examples:
Input: arr[] = {12, 3, 5, 6, 7, 17}, K = 2
Output: 1
Explanation: Considering two subsets {5, 6} and {3, 7}, the difference between their sum = (5 + 6) – (3 + 7) = (11 – 10) = 1, which is minimum possible.Input: arr[] = {10, 10, 10, 10, 10, 2}, K = 3
Output: 8
Explanation: Considering two subsets {10, 10, 10} and {10, 10, 2}, the difference between their sum = (10 + 10 + 10) – (10 + 10 + 2) = (30 – 22) = 8.
Naive Approach: The simplest approach to solve the given problem is to generate all possible subsets of size K and choose every pair of subsets of size K such that each array element can occur in at most 1 subset. After finding all possible pairs of subsets, print the minimum difference between the sum of elements for each pair of subsets.
Time Complexity: O(3N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using Dynamic Programming. To implement this approach, the idea is to use 3D-array, say dp[][][], to store the states of each recursive call.
Follow the steps below to solve the problem:
- Initialize an auxiliary array, say dp[][][], where dp[i][S1][S2] stores the sum of the two subsets formed till every ith index.
- Declare a recursive function, say minimumDifference(arr, N, K1, K2, S1, S2), that accepts an array, the current size of the array, the number of elements stored in the subsets(K1 and K2), and the sum of elements in each subset as parameters.
- Base Case: If the number of elements in the array is N, and the value of K1 and K2 is 0, then return the absolute difference between S1 and S2.
- If the result of the current state is already computed, return the result.
- Store the value returned by including the Nth element in the first subset and recursively call for the next iterations as minimumDifference(arr, N – 1, K1 – 1, K2, S1 + arr[N – 1], S2).
- Store the value returned by including the Nth element in the first subset and recursively call for the next iterations as minimumDifference(arr, N – 1, K1, K2 – 1, S1, S2 + arr[N – 1]).
- Store the value returned by not including the Nth element in either of the subsets and recursively call for the next iterations as minimumDifference(arr, N – 1, K1, K2, S1, S2).
- Store the minimum of all the values returned by the above three recursive calls in the current state i.e., dp[N][S1][S2], and return its value.
- After completing the above steps, print the value returned by the function minimumDifference(arr, N, K, K, 0, 0).
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Stores the values at recursive states int dp[100][100][100]; // Function to find the minimum difference // between sum of two K-length subsets int minSumDifference( int * arr, int n, int k1, int k2, int sum1, int sum2) { // Base Case if (n < 0) { // If k1 and k2 are 0, then // return the absolute difference // between sum1 and sum2 if (k1 == 0 && k2 == 0) { return abs (sum1 - sum2); } // Otherwise, return INT_MAX else { return INT_MAX; } } // If the result is already // computed, return the result if (dp[n][sum1][sum2] != -1) { return dp[n][sum1][sum2]; } // Store the 3 options int op1 = INT_MAX; int op2 = INT_MAX; int op3 = INT_MAX; // Including the element in first subset if (k1 > 0) { op1 = minSumDifference(arr, n - 1, k1 - 1, k2, sum1 + arr[n], sum2); } // Including the element in second subset if (k2 > 0) { op2 = minSumDifference(arr, n - 1, k1, k2 - 1, sum1, sum2 + arr[n]); } // Not including the current element // in both the subsets op3 = minSumDifference(arr, n - 1, k1, k2, sum1, sum2); // Store minimum of 3 values obtained dp[n][sum1][sum2] = min(op1, min(op2, op3)); // Return the value for // the current states return dp[n][sum1][sum2]; } // Driver Code int main() { int arr[] = { 12, 3, 5, 6, 7, 17 }; int K = 2; int N = sizeof (arr) / sizeof (arr[0]); memset (dp, -1, sizeof (dp)); cout << minSumDifference(arr, N - 1, K, K, 0, 0); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ // Stores the values at recursive states static int [][][] dp = new int [ 100 ][ 100 ][ 100 ]; // Function to find the minimum difference // between sum of two K-length subsets static int minSumDifference( int [] arr, int n, int k1, int k2, int sum1, int sum2) { // Base Case if (n < 0 ) { // If k1 and k2 are 0, then // return the absolute difference // between sum1 and sum2 if (k1 == 0 && k2 == 0 ) { return Math.abs(sum1 - sum2); } // Otherwise, return INT_MAX else { return Integer.MAX_VALUE; } } // If the result is already // computed, return the result if (dp[n][sum1][sum2] != - 1 ) { return dp[n][sum1][sum2]; } // Store the 3 options int op1 = Integer.MAX_VALUE; int op2 = Integer.MAX_VALUE; int op3 = Integer.MAX_VALUE; // Including the element in first subset if (k1 > 0 ) { op1 = minSumDifference(arr, n - 1 , k1 - 1 , k2, sum1 + arr[n], sum2); } // Including the element in second subset if (k2 > 0 ) { op2 = minSumDifference(arr, n - 1 , k1, k2 - 1 , sum1, sum2 + arr[n]); } // Not including the current element // in both the subsets op3 = minSumDifference(arr, n - 1 , k1, k2, sum1, sum2); // Store minimum of 3 values obtained dp[n][sum1][sum2] = Math.min(op1, Math.min(op2, op3)); // Return the value for // the current states return dp[n][sum1][sum2]; } // Driver Code public static void main (String[] args) { int arr[] = { 12 , 3 , 5 , 6 , 7 , 17 }; int K = 2 ; int N = arr.length; for ( int [][] row:dp) { for ( int [] innerrow : row) { Arrays.fill(innerrow,- 1 ); } } System.out.println(minSumDifference(arr, N - 1 , K, K, 0 , 0 )); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 program for the above approach import sys # Stores the values at recursive states dp = [[[ - 1 for i in range ( 100 )] for i in range ( 100 )] for i in range ( 100 )] # Function to find the minimum difference # between sum of two K-length subsets def minSumDifference(arr, n, k1, k2, sum1, sum2): global dp # Base Case if (n < 0 ): # If k1 and k2 are 0, then # return the absolute difference # between sum1 and sum2 if (k1 = = 0 and k2 = = 0 ): return abs (sum1 - sum2) # Otherwise, return INT_MAX else : return sys.maxsize + 1 # If the result is already # computed, return the result if (dp[n][sum1][sum2] ! = - 1 ): return dp[n][sum1][sum2] # Store the 3 options op1 = sys.maxsize + 1 op2 = sys.maxsize + 1 op3 = sys.maxsize + 1 # Including the element in first subset if (k1 > 0 ): op1 = minSumDifference(arr, n - 1 , k1 - 1 , k2, sum1 + arr[n], sum2) # Including the element in second subset if (k2 > 0 ): op2 = minSumDifference(arr, n - 1 , k1, k2 - 1 , sum1, sum2 + arr[n]) # Not including the current element # in both the subsets op3 = minSumDifference(arr, n - 1 , k1, k2, sum1, sum2) # Store minimum of 3 values obtained dp[n][sum1][sum2] = min (op1, min (op2, op3)) # Return the value for # the current states return dp[n][sum1][sum2] # Driver Code if __name__ = = '__main__' : arr = [ 12 , 3 , 5 , 6 , 7 , 17 ] K = 2 N = len (arr) #memset(dp, -1, sizeof(dp)) print (minSumDifference(arr, N - 1 , K, K, 0 , 0 )) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG{ // Stores the values at recursive states static int [,,] dp = new int [100, 100, 100]; // Function to find the minimum difference // between sum of two K-length subsets static int minSumDifference( int [] arr, int n, int k1, int k2, int sum1, int sum2) { // Base Case if (n < 0) { // If k1 and k2 are 0, then // return the absolute difference // between sum1 and sum2 if (k1 == 0 && k2 == 0) { return Math.Abs(sum1 - sum2); } // Otherwise, return INT_MAX else { return Int32.MaxValue; } } // If the result is already // computed, return the result if (dp[n, sum1, sum2] != -1) { return dp[n, sum1, sum2]; } // Store the 3 options int op1 = Int32.MaxValue; int op2 = Int32.MaxValue; int op3 = Int32.MaxValue; // Including the element in first subset if (k1 > 0) { op1 = minSumDifference(arr, n - 1, k1 - 1, k2, sum1 + arr[n], sum2); } // Including the element in second subset if (k2 > 0) { op2 = minSumDifference(arr, n - 1, k1, k2 - 1, sum1, sum2 + arr[n]); } // Not including the current element // in both the subsets op3 = minSumDifference(arr, n - 1, k1, k2, sum1, sum2); // Store minimum of 3 values obtained dp[n, sum1, sum2] = Math.Min(op1, Math.Min(op2, op3)); // Return the value for // the current states return dp[n, sum1, sum2]; } // Driver Code static public void Main() { int [] arr = { 12, 3, 5, 6, 7, 17 }; int K = 2; int N = arr.Length; for ( int i = 0; i < 100; i++) { for ( int j = 0; j < 100; j++) { for ( int k = 0; k < 100; k++) { dp[i, j, k] = -1; } } } Console.WriteLine(minSumDifference(arr, N - 1, K, K, 0, 0)); } } // This code is contributed by rag2127 |
Javascript
<script> // Javascript program for the above approach // Stores the values at recursive states let dp = new Array(100); for (let i = 0; i < 100; i++) { dp[i] = new Array(100); for (let j = 0; j < 100; j++) { dp[i][j] = new Array(100); for (let k = 0; k < 100; k++) dp[i][j][k] = -1; } } // Function to find the minimum difference // between sum of two K-length subsets function minSumDifference(arr, n, k1, k2, sum1, sum2) { // Base Case if (n < 0) { // If k1 and k2 are 0, then // return the absolute difference // between sum1 and sum2 if (k1 == 0 && k2 == 0) { return Math.abs(sum1 - sum2); } // Otherwise, return INT_MAX else { return Number.MAX_VALUE; } } // If the result is already // computed, return the result if (dp[n][sum1][sum2] != -1) { return dp[n][sum1][sum2]; } // Store the 3 options let op1 = Number.MAX_VALUE; let op2 = Number.MAX_VALUE; let op3 = Number.MAX_VALUE; // Including the element in first subset if (k1 > 0) { op1 = minSumDifference(arr, n - 1, k1 - 1, k2, sum1 + arr[n], sum2); } // Including the element in second subset if (k2 > 0) { op2 = minSumDifference(arr, n - 1, k1, k2 - 1, sum1, sum2 + arr[n]); } // Not including the current element // in both the subsets op3 = minSumDifference(arr, n - 1, k1, k2, sum1, sum2); // Store minimum of 3 values obtained dp[n][sum1][sum2] = Math.min(op1, Math.min(op2, op3)); // Return the value for // the current states return dp[n][sum1][sum2]; } // Driver Code let arr = [12, 3, 5, 6, 7, 17 ]; let K = 2; let N = arr.length; document.write(minSumDifference(arr, N - 1, K, K, 0, 0)); // This code is contributed by patel2127 </script> |
1
Time Complexity: O(N*S2), where S is the sum of elements of the given array
Auxiliary Space: O(N*S2)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!