Given an integer array of size 2*n, partition the array into two arrays of equal length such that the absolute difference between the sums of these two arrays is minimum. Return this minimum difference. To partition the array, allocate each element to one of two arrays.
Examples :
Input: arr[] = {7, 3, 2, 8}
Output: 0
Explanation :
Subset1 = {2, 8}, sum of Subset1 = 10
Subset2 = {7, 3}, sum of Subset2 = 10
Absolute Difference = 0Input: arr[] = {1, -1, 1, 5, 2, -9}
Output: 3
Explanation:
Subset1 = {2, 5, -9}, sum of Subset1 = -2
Subset2 = {-1, 1, 1}, sum of Subset2 = 1
Absolute Difference = 3
Constraints:
- 1 <= n <= 15
- -107 <= arr[i] <= 107
Brute force Approach (Using Recursion):
In this process, we essentially explore all possible combinations of splitting the elements into two arrays recursively and select the one that meets the length equality requirement while minimizing the difference in sum between the two arrays.
Consider the below example :
Example array
Dry Run
Explanation :
- Start with two empty arrays, Array 1 and Array 2.
- The first element, which is 7 in this case, has two choices: it can either be placed in Array 1 or Array 2. Visualize this as the second level of a decision tree.
- Move to the next element, 3. It has two options: join the same array as 7 or go into the other array. This expands our tree further.
- Continue this process for the remaining elements, 2 and 8.
- Since all the elements from the original array have been used, we now need to filter the options based on the requirement that both arrays’ lengths should be equal.
- Among the desired options, choose the one where the difference in the sums of the two subsets is minimum. This is the solution you are seeking.
- Base Case: After considering all array elements and making choices about their placement into two subsets, we calculate the absolute difference between the sums of these subsets. This difference is then compared to the current minimum difference.
Below is the implementation of the above idea:
C++
#include <climits>#include <cstdlib>#include <iostream>#include <vector>using namespace std;int min_diff = INT_MAX;void solve(vector<int>& nums, int index, int arr1_sum, int arr2_sum, int arr1_length, int arr2_length){ if (arr1_length > nums.size() / 2 || arr2_length > nums.size() / 2) { return; } if (index == nums.size()) { int diff = abs(arr1_sum - arr2_sum); min_diff = min(min_diff, diff); return; } solve(nums, index + 1, arr1_sum + nums[index], arr2_sum, arr1_length + 1, arr2_length); solve(nums, index + 1, arr1_sum, arr2_sum + nums[index], arr1_length, arr2_length + 1);}int main(){ vector<int> arr = { 3, 7, 3, 9 }; solve(arr, 0, 0, 0, 0, 0); cout << min_diff << endl; return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { static int min = Integer.MAX_VALUE; public static void solve(int[] nums, int index, int arr1_sum, int arr2_sum, int arr1_length, int arr2_length) { if (arr1_length > nums.length / 2 || arr2_length > nums.length / 2) { return; } if (index == nums.length) { int diff = arr1_sum - arr2_sum; min = Math.min(min, Math.abs(diff)); return; } solve(nums, index + 1, arr1_sum + nums[index], arr2_sum, arr1_length + 1, arr2_length); solve(nums, index + 1, arr1_sum, arr2_sum + nums[index], arr1_length, arr2_length + 1); } public static void main(String[] args) { int[] arr = { 3, 7, 3, 9 }; solve(arr, 0, 0, 0, 0, 0); System.out.println(min); }} |
Python
class GFG: min_val = float('inf') @staticmethod def solve(nums, index, arr1_sum, arr2_sum, arr1_length, arr2_length): if arr1_length > len(nums) // 2 or arr2_length > len(nums) // 2: return if index == len(nums): diff = arr1_sum - arr2_sum GFG.min_val = min(GFG.min_val, abs(diff)) return GFG.solve(nums, index + 1, arr1_sum + nums[index], arr2_sum, arr1_length + 1, arr2_length) GFG.solve(nums, index + 1, arr1_sum, arr2_sum + nums[index], arr1_length, arr2_length + 1) @staticmethod def main(): arr = [3, 7, 3, 9] GFG.solve(arr, 0, 0, 0, 0, 0) print(GFG.min_val)if __name__ == "__main__": GFG.main() |
C#
using System;class GFG { static int min = int.MaxValue; // Function to recursively explore all possible splits // and calculate the minimum difference public static void Solve(int[] nums, int index, int arr1_sum, int arr2_sum, int arr1_length, int arr2_length) { // Base case: if either of the arrays has exceeded // half the length, stop exploring if (arr1_length > nums.Length / 2 || arr2_length > nums.Length / 2) { return; } // Base case: if reached the end of the array, // calculate and update the minimum difference if (index == nums.Length) { int diff = arr1_sum - arr2_sum; min = Math.Min(min, Math.Abs(diff)); return; } // Explore two possibilities: including the current // element in the first array or the second array Solve(nums, index + 1, arr1_sum + nums[index], arr2_sum, arr1_length + 1, arr2_length); Solve(nums, index + 1, arr1_sum, arr2_sum + nums[index], arr1_length, arr2_length + 1); } public static void Main(string[] args) { // Input array int[] arr = { 3, 7, 3, 9 }; // Solve the problem and print the minimum // difference Solve(arr, 0, 0, 0, 0, 0); Console.WriteLine(min); }} |
Javascript
// JavaScript code for the above approach:let min_diff = Number.MAX_SAFE_INTEGER;function solve(nums, index, arr1_sum, arr2_sum, arr1_length, arr2_length) { // Base case: if either array length exceeds // half of the nums' size, return if (arr1_length > nums.length / 2 || arr2_length > nums.length / 2) { return; } // If all elements have been considered if (index === nums.length) { const diff = Math.abs(arr1_sum - arr2_sum); min_diff = Math.min(min_diff, diff); return; } // Recursively consider two possibilities: including // the current number in arr1 or arr2 solve(nums, index + 1, arr1_sum + nums[index], arr2_sum, arr1_length + 1, arr2_length); solve(nums, index + 1, arr1_sum, arr2_sum + nums[index], arr1_length, arr2_length + 1);}const arr = [3, 7, 3, 9];solve(arr, 0, 0, 0, 0, 0);console.log(min_diff); |
Output
2
Time Complexity : O( 2n )
Auxiliary Space : O(1)
Optimised Approach (Using Meet in the Middle technique):
- If we were to initially apply a brute force approach, checking all conceivable subsets, the time complexity would grow to O(2N), with N representing the array’s length. However, as N increases in magnitude, it becomes prone to encountering Time Limit Exceeded (TLE) errors.
- The crucial idea here is to partition the array into two segments, where in we traverse one section while applying binary search within the other. This approach effectively diminishes the time complexity.
- We are tasked with splitting a collection of 2*N numbers, represented as array A, into two equal parts, a1 and a2, each containing N numbers. Once we have successfully extracted N numbers for a1, we inherently determine the contents of a2. Consequently, the problem can be simplified to the task of selecting N numbers to populate a1.
- We choose some numbers from both the first sub-array and the second sub-array to construct the a1. If we decide to select x numbers from the first sub-array, it becomes imperative that we choose precisely N – x numbers from the second sub-array to compose the a1 array.
- Next, we proceed by iterating through the first half of the array, identifying all possible subarrays, and documenting the-subarray size and sum of elements of subarray .
- We then store all these size-sum pairs in a vector called “Left.” In a similar fashion, we create a vector named “Right” for the second sub-array
- Lastly, our task simplifies to iterating through all the potential size-sum pairs within the “Left” . Let’s assume we have a subarray with a size of s1 and a sum of elements sum_1. In this context, we aim to discover a pair with a size of N – s1 and a sum as close as possible to (TotalSum-2*sum_1)/2 in the “Right” . This can be accomplished through two pointer approach(less efficient as it increases time complexity) or Binary Search. (most efficient).
Why we are searching (TotalSum – 2*a)/2 ??
We want to minimize abs(sum2 – sum1).
- We know TotalSum=sum1+sum2 so, sum2 = TotalSum – sum1 .
- Our aim becomes to minimize abs(TotalSum – 2sum1)
- Let say from left part we take a subset of size x ,with sum as a, then from right part we need to take a subset of size of n-x ,let’s say its sum is b.
- Therefore we can say sum1 = a+b
- As our Objective was to minimize abs(T – 2 * sum1), at the best possible outcome we can have abs() = 0 which will happen when
- 2 * sum1 = T
- 2 * (a+b) = T
- b = (T-2*a)/2
Below is the implementation of the above approach:
C++
#include <algorithm>#include <iostream>#include <numeric>#include <vector>using namespace std;class Solution {public: int minimumDifference(vector<int>& arr) { // Divide array into 2 equal parts each os size N int n = arr.size(); int N = n / 2; vector<vector<int> > left(N + 1), right(N + 1); // To find the sum of the all the elements of array int total_sum = 0; total_sum = accumulate(arr.begin(), arr.end(), 0); // Find All possible sum possible and store them for (int mask_itr = 0; mask_itr < (1 << N); ++mask_itr) { int index = 0; int left_sum = 0; int right_sum = 0; for (int i = 0; i < N; ++i) { if (mask_itr & (1 << i)) { index++; left_sum += arr[i]; right_sum += arr[i + N]; } } left[index].push_back(left_sum); right[index].push_back(right_sum); } // Sort the right half to perform BS for (int index = 0; index <= N; ++index) { sort(right[index].begin(), right[index].end()); } // initializing result int result = min(abs(total_sum - 2 * left[N][0]), abs(total_sum - 2 * right[N][0])); // start traversing over left for (int index = 1; index < N; ++index) { for (auto& a : left[index]) { int b = (total_sum - 2 * a) / 2; int rightindex = N - index; auto& v = right[rightindex]; auto itr = lower_bound(v.begin(), v.end(), b); if (itr != v.end()) result = min( result, abs(total_sum - 2 * (a + (*itr)))); } } return result; }};int main(){ // Example usage of your Solution class vector<int> arr = { 3, 8, 6, 3 }; Solution solution; int result = solution.minimumDifference(arr); cout << "Minimum Difference: " << result << endl; return 0;} |
Java
/*package whatever //do not write package name here */import java.util.*;class GFG { public static int minimumDifference(int[] arr) { int n = arr.length; int N = n / 2; List<Integer>[] left = new ArrayList[N + 1]; List<Integer>[] right = new ArrayList[N + 1]; for (int i = 0; i <= N; i++) { left[i] = new ArrayList<>(); right[i] = new ArrayList<>(); } int totalSum = 0; for (int num : arr) { totalSum += num; } for (int maskItr = 0; maskItr < (1 << N); maskItr++) { int index = 0; int leftSum = 0; int rightSum = 0; for (int i = 0; i < N; i++) { if ((maskItr & (1 << i)) != 0) { index++; leftSum += arr[i]; rightSum += arr[i + N]; } } left[index].add(leftSum); right[index].add(rightSum); } for (int index = 0; index <= N; index++) { right[index].sort(Integer::compareTo); } int result = Math.min( Math.abs(totalSum - 2 * left[N].get(0)), Math.abs(totalSum - 2 * right[N].get(0))); for (int index = 1; index < N; index++) { for (Integer a : left[index]) { int b = (totalSum - 2 * a) / 2; int rightIndex = N - index; List<Integer> v = right[rightIndex]; int idx = lowerBound(v, b); if (idx != v.size()) { result = Math.min( result, Math.abs(totalSum - 2 * (a + v.get(idx)))); } } } return result; } // Custom implementation of lower_bound function private static int lowerBound(List<Integer> arr, int target) { int left = 0; int right = arr.size(); while (left < right) { int mid = left + (right - left) / 2; if (arr.get(mid) < target) { left = mid + 1; } else { right = mid; } } return left; } public static void main(String[] args) { int arr[] = { 3, 8, 6, 3 }; int ans = minimumDifference(arr); System.out.println(ans); }} |
C#
using System;using System.Collections.Generic;class GFG{ // Function to find the minimum difference public static int MinimumDifference(int[] arr) { int n = arr.Length; int N = n / 2; // Arrays to store subsets of sums List<int>[] left = new List<int>[N + 1]; List<int>[] right = new List<int>[N + 1]; for (int i = 0; i <= N; i++) { left[i] = new List<int>(); right[i] = new List<int>(); } int totalSum = 0; foreach (int num in arr) { totalSum += num; } // Generate subsets and calculate sums for (int maskItr = 0; maskItr < (1 << N); maskItr++) { int index = 0; int leftSum = 0; int rightSum = 0; // Calculate sums for left and right subsets for (int i = 0; i < N; i++) { if ((maskItr & (1 << i)) != 0) { index++; leftSum += arr[i]; rightSum += arr[i + N]; } } left[index].Add(leftSum); right[index].Add(rightSum); } // Sort the right subsets for (int index = 0; index <= N; index++) { right[index].Sort(); } // Initialize the result with the total sum difference int result = Math.Min( Math.Abs(totalSum - 2 * left[N][0]), Math.Abs(totalSum - 2 * right[N][0])); // Iterate through subsets and find the minimum difference for (int index = 1; index < N; index++) { foreach (int a in left[index]) { int b = (totalSum - 2 * a) / 2; int rightIndex = N - index; List<int> v = right[rightIndex]; int idx = LowerBound(v, b); if (idx != v.Count) { // Update result if a better difference is found result = Math.Min( result, Math.Abs(totalSum - 2 * (a + v[idx]))); } } } return result; } // Custom implementation of lower_bound function private static int LowerBound(List<int> arr, int target) { int left = 0; int right = arr.Count; // Binary search to find the lower bound while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } // Driver code public static void Main(string[] args) { int[] arr = { 3, 8, 6, 3 }; int ans = MinimumDifference(arr); Console.WriteLine("Minimun Difference: " + ans); }} |
Javascript
// Function to find the minimum difference between subsetsfunction minimumDifference(arr) { const n = arr.length; const N = Math.floor(n / 2); // Arrays to store subsets of sums const left = new Array(N + 1).fill(null).map(() => []); const right = new Array(N + 1).fill(null).map(() => []); let totalSum = 0; // Calculate the total sum of elements in the array arr.forEach((num) => { totalSum += num; }); // Generate subsets and calculate sums for (let maskItr = 0; maskItr < (1 << N); maskItr++) { let index = 0; let leftSum = 0; let rightSum = 0; // Calculate sums for left and right subsets based on the bitmask for (let i = 0; i < N; i++) { if (maskItr & (1 << i)) { index++; leftSum += arr[i]; rightSum += arr[i + N]; } } left[index].push(leftSum); right[index].push(rightSum); } // Sort the right subsets for (let index = 0; index <= N; index++) { right[index].sort((a, b) => a - b); } // Initialize result with the total sum difference between subsets let result = Math.min( Math.abs(totalSum - 2 * left[N][0]), Math.abs(totalSum - 2 * right[N][0]) ); // Iterate through subsets and find the minimum difference for (let index = 1; index < N; index++) { left[index].forEach((a) => { const b = (totalSum - 2 * a) / 2; const rightIndex = N - index; const v = right[rightIndex]; const idx = lowerBound(v, b); if (idx !== v.length) { // Update result if a better difference is found result = Math.min( result, Math.abs(totalSum - 2 * (a + v[idx])) ); } }); } return result;}// Custom implementation of lower_bound functionfunction lowerBound(arr, target) { let left = 0; let right = arr.length; // Binary search to find the lower bound while (left < right) { const mid = Math.floor(left + (right - left) / 2); if (arr[mid] < target) { left = mid + 1; } else { right = mid; } } return left;}// Driver codeconst arr = [3, 8, 6, 3];const ans = minimumDifference(arr);console.log("Minimum Difference: " + ans); |
Output
Minimum Difference: 2
Time Complexity : O(2N . log(2N))
Auxiliary Space : O( N2 )
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!
Share your thoughts in the comments
