4

Note: I know this question has been asked here, but I didn't properly understand the solution, and I don't have enough points to comment to clarify my query. (I'm a beginner on SO)

Question: Given an array, of size n, divide the array into 2 non contiguous subarrays of size n/2 & n/2 (if n is even), and (n-1)/2 & (n+1)/2, (if n is odd), such that the absolute difference between the sums of the 2 subarrays is minimum.

Example:

4 5 3 55 -3 23 3 20 100 90

Answer: 0. Explanation: {100, 20, 23, 4, 3} and {5, 55, -3, 3, 90}, both of which sum to 150.

I know greedy approach won't work for this, and feel that this involves dynamic programming. However, I am unable to model a solution that ensures that the subarrays being considered are of equal size, my solution generates minimum difference subarrays of arbitrary size, which is a general partition problem.

I am also unsure whether making a table is a good idea, because the numbers can be huge. (Although its certain that all input is within bounds for int).

Can anyone provide me an algorithm that I could apply?

Here is the link to the question that has already been asked (and answered): Dividing an array into two subsets of equal sizes having minimum difference in sum of values.

Community
  • 1
  • 1
Utkarsh
  • 91
  • 1
  • 4

3 Answers3

2

A recursive implementation (Java):

private static long minimalDiff(int[] nums, int sumA, int sumB, int indexA, int indexB) {
    int index = indexA + indexB + 2;
    if (index == nums.length) {
        return Math.abs(sumA - sumB);
    } else if (Math.max(indexA, indexB) * 2 > nums.length - 1) {
        return Integer.MAX_VALUE;
    } else if (Math.abs(sumA + nums[index] - sumB) < Math.abs(sumB + nums[index] - sumA)){
        long result = minimalDiff(nums, sumA + nums[index], sumB, indexA + 1, indexB);
        if (result > 0) {
            result = Math.min(result, minimalDiff(nums, sumB + nums[index], sumA, indexB + 1, indexA));
        }
        return result;
    } else {
        long result = minimalDiff(nums, sumB + nums[index], sumA, indexB + 1, indexA);
        if (result > 0) {
            result = Math.min(result, minimalDiff(nums, sumA + nums[index], sumB, indexA + 1, indexB));
        }
        return result;
    }
}

public static long minimalDiff(int[] num) {
    if (num == null || num.length < 2){
        throw new IllegalArgumentException("num");
    }
    return minimalDiff(num, 0, 0, -1, -1);
}

public static void main(String[] args) {
    int [] test= {4, 5, 3, 55, -3, 23, 3, 20, 100, 90};
    System.out.println("Answer: "+minimalDiff(test));
}

It prints:

Answer: 0
David Pérez Cabrera
  • 4,960
  • 2
  • 23
  • 37
1

Here is an c++ implementation for the problem using recursion.

#include<bits/stdc++.h>
using namespace std;
void solve(int ele,int currSum,int index,int maxe,int * arr,int & answer,int sum,int n){
//      cout<<index<<" "<<ele<<" "<<currSum;
        if(ele==maxe){
            int ssum=sum-currSum;
            if(abs(currSum-ssum)<answer)
                answer=abs(currSum-ssum);
            return;
        }
        if(index>=n){
            return;
        }
        solve(ele+1,currSum+arr[index],index+1,maxe,arr,answer,sum,n);
        solve(ele,currSum,index+1,maxe,arr,answer,sum,n);
}
int FindMinimumDifference(int *arr,int n){
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=arr[i];
    }
    int answer=INT_MAX;
    solve(0,0,0,n/2,arr,answer,sum,n);
    return answer;
}
int main(){
    int n,x;
    cin>>n;
    int * arr=new int[n];
    for(int i=0;i<n;i++){
        cin>>x;
        arr[i]=x;
    }
    cout<<FindMinimumDifference(arr,n);
    return 0;
}
user8902733
  • 11
  • 2
0

If one subset of half size is formed, the remaining elements form the other subset. We initialize current set as empty and one by one build it. There are two possibilities for every element, either it is part of current set, or it is part of the remaining elements (other subset). We consider both possibilities for every element. When the size of current set becomes n/2, we check whether this solutions is better than the best solution available so far. If it is, then we update the best solution.

Manan Chhajer
  • 1