Minimize Subset sum difference after deleting K elements of Array
Given an array arr[] containing N integers and an integer K, the task is to minimize the subset-sum difference after removing K elements from the given array.
Note: The subsets must be non-empty.
Examples:
Input: arr[] = {7, 9, 5, 8, 1, 3}, K = 2
Output: -23
Explanation: Remove 5 and 3 from the array and form subsets [1] and [7, 8, 9].
The subset difference of these subset is 1 – 24 = -23 that is the minimum possible difference.Input: arr[] = {7, 9, 5, 8}, K = 3
Output: -1
Explanation: If 3 elements are removed it is not possible to form two non-empty subsets.
Approach: The problem can be solved using recursion based on the following idea:
For each element of the array there are 3 choices: either it can be deleted or be a part of any of the two subsets. Form all the possible subsets after deleting K elements and find the one where the difference of subset sums is the minimum.
Instead of considering the three options for each array element, only two options can be considered: either deleted or part of first subset (because if the sum of first subset elements are known then the other subset sum = array sum – first subset sum)
Follow the steps mentioned to solve the problem:
- Calculate the sum of all the array elements.
- Iterate recursively for each array element:
- Delete this if K elements are not already deleted and continue for the next index.
- Consider this as part of one subset.
- If the whole array is traversed, check the difference between two subset sums.
- The minimum difference is the required answer.
Below is the implementation for the above-mentioned approach:
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; int mini = INT_MAX; // Function to form all possible subsets void subset(vector< int > arr, int index, int sum, int total) { if (index >= arr.size()) { if (sum != 0) mini = min(mini, sum - (total - sum)); return ; } subset(arr, index + 1, sum + arr[index], total); subset(arr, index + 1, sum, total); } // Function to get the minimum difference static void print( int index, vector< int >& arr, int total, vector< int >& ans) { if (total == 0) { int sum = 0; for ( int elements : ans) { sum += elements; } // Function call to form subset subset(ans, 0, 0, sum); return ; } if (index >= arr.size()) { return ; } ans.push_back(arr[index]); print(index + 1, arr, total - 1, ans); ans.pop_back(); print(index + 1, arr, total, ans); } // Utility function to solve the problem void solve(vector< int >& arr, int N) { int selected = arr.size() - N; if (selected <= 1) { cout << -1; return ; } vector< int > ans; print(0, arr, selected, ans); } // Driver code int main() { vector< int > arr = { 7, 9, 5, 8, 1, 3 }; int N = 2; solve(arr, N); cout << (mini); return 0; } // This code is contributed by rakeshsahni |
Java
// Java code to implement the above approach import java.io.*; import java.util.*; class GFG { static int min = Integer.MAX_VALUE; // Function to form all possible subsets static void subset(List<Integer> arr, int index, int sum, int total) { if (index >= arr.size()) { if (sum != 0 ) min = Math.min(min, sum - (total - sum)); return ; } subset(arr, index + 1 , sum + arr.get(index), total); subset(arr, index + 1 , sum, total); } // Function to get the minimum difference static void print( int index, int arr[], int total, List<Integer> ans) { if (total == 0 ) { int sum = 0 ; for ( int elements : ans) { sum += elements; } // Function call to form subset subset(ans, 0 , 0 , sum); return ; } if (index >= arr.length) { return ; } ans.add(arr[index]); print(index + 1 , arr, total - 1 , ans); ans.remove(ans.size() - 1 ); print(index + 1 , arr, total, ans); } // Utility function to solve the problem public static void solve( int arr[], int N) { int selected = arr.length - N; if (selected <= 1 ) { System.out.println(- 1 ); return ; } List<Integer> ans = new ArrayList<>(); print( 0 , arr, selected, ans); } // Driver code public static void main(String[] args) { int arr[] = { 7 , 9 , 5 , 8 , 1 , 3 }; int N = 2 ; solve(arr, N); System.out.println(min); } } |
Python3
# Python code to implement the above approach import sys # Function to form all possible subsets def subset(arr,index, sum ,total): global mini if (index > = len (arr)): if ( sum ! = 0 ): mini = min (mini, sum - (total - sum )) return subset(arr, index + 1 , sum + arr[index], total) subset(arr, index + 1 , sum , total) # Function to get the minimum difference def Print (index,arr,total,ans): if (total = = 0 ): sum = 0 for elements in ans: sum + = elements # Function call to form subset subset(ans, 0 , 0 , sum ) return if (index > = len (arr)): return ans.append(arr[index]) Print (index + 1 , arr, total - 1 , ans) ans.pop() Print (index + 1 , arr, total, ans) # Utility function to solve the problem def solve(arr,N): selected = len (arr) - N if (selected < = 1 ): print ( - 1 ) return ans = [] Print ( 0 , arr, selected, ans) # Driver code if __name__ = = "__main__" : mini = sys.maxsize arr = [ 7 , 9 , 5 , 8 , 1 , 3 ] N = 2 solve(arr, N) print (mini) # This code is contributed by shinjanpatra |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG { static int min = Int32.MaxValue; // Function to form all possible subsets static void subset(List< int > arr, int index, int sum, int total) { if (index >= arr.Count) { if (sum != 0) min = Math.Min(min, sum - (total - sum)); return ; } subset(arr, index + 1, sum + arr[index], total); subset(arr, index + 1, sum, total); } // Function to get the minimum difference static void print( int index, int [] arr, int total, List< int > ans) { if (total == 0) { int sum = 0; foreach ( int elements in ans) { sum += elements; } // Function call to form subset subset(ans, 0, 0, sum); return ; } if (index >= arr.Length) { return ; } ans.Add(arr[index]); print(index + 1, arr, total - 1, ans); ans.RemoveAt(ans.Count - 1); print(index + 1, arr, total, ans); } // Utility function to solve the problem public static void solve( int [] arr, int N) { int selected = arr.Length - N; if (selected <= 1) { Console.Write(-1); return ; } List< int > ans = new List< int >(); print(0, arr, selected, ans); } // Driver Code public static void Main() { int [] arr = { 7, 9, 5, 8, 1, 3 }; int N = 2; solve(arr, N); Console.Write(min); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code to implement the above approach let mini = Number.MAX_VALUE; // Function to form all possible subsets function subset(arr,index,sum,total) { if (index >= arr.length) { if (sum != 0) mini = Math.min(mini, sum - (total - sum)); return ; } subset(arr, index + 1, sum + arr[index], total); subset(arr, index + 1, sum, total); } // Function to get the minimum difference function print(index,arr,total,ans) { if (total == 0) { sum = 0; for (let elements of ans) { sum += elements; } // Function call to form subset subset(ans, 0, 0, sum); return ; } if (index >= arr.length) { return ; } ans.push(arr[index]); print(index + 1, arr, total - 1, ans); ans.pop(); print(index + 1, arr, total, ans); } // Utility function to solve the problem function solve(arr,N) { let selected = arr.length - N; if (selected <= 1) { document.write(-1); return ; } let ans = []; print(0, arr, selected, ans); } // Driver code let arr = [ 7, 9, 5, 8, 1, 3 ]; let N = 2; solve(arr, N); document.write(mini); // This code is contributed by shinjanpatra </script> |
-23
Time Complexity: O(2N)
Auxiliary Space: O(N)