Divide the array in two subarray such that difference of the sum is minimum?

Question

Divide the array in two subarrays of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subarray must be n/2 and if n is odd, then size of one subarray must be (n-1)/2 and size of other subset must be (n+1)/2.

Comments

prakash, can you share example ? am not able catch this.

Answer 1

void display(int list[], int n)
{
    int i;
    for(i = 0 ; i < n; ++ i)
    {
        printf("  %d", list[i]);
    }
    printf("\n");
}

int find_diff(int num1, int num2)
{
    if(num1 > num2)
        return num1 - num2;
    else
        return num2 - num1;
}

void balance(int sum2, int sum1, int a2[], int a1[], int n)
{
    int diff = (sum2 - sum1)/2;
    int min, bal = 999999;
    int idx1 , idx2, temp1, temp2;
    int i = 0; int j = 0;
    int FLAG = FALSE;
    while(i < n && j < n)
    {
        min = a2[j] - a1[i];
        if (min > 0) 
        {
            if (min < diff * 2)
            {
                min = find_diff (min, diff);
                if (bal > min)
                {
                    bal = min;
                    idx1 = i;
                    idx2 = j;
                    i++;
                    FLAG = TRUE;
                }
                else
                    j++;
            }
            else 
                j++;
        }
        else
            i++;
    }
    if (FLAG)
    {
        temp1 = a1[idx1];
        temp2 = a2[idx2];
        for (i = idx1; i >= 0; i--)
        {
            if(temp2 > a1[i - 1])
                a1[i] = a1[i - 1];
            else
            {
                a1[i] = temp2;
                break;
            }

        }
        for (i = idx2; i < n; i++)
        {
            if(temp1 < a2[i + 1])
                a2[i] = a2[i + 1];
            else
            {
                a2[i] = temp1;
                break;
            }
        }

        sum1 = sum1 - temp1 + temp2;
        sum2 = sum2 - temp2 + temp1;

        if (sum2 > sum1)
           balance(sum2, sum1, a2, a1, n);
        else
           balance(sum1, sum2, a1, a2, n);
    }
    else
    {
        printf("\n\n SUM = %d\t",sum1);
        display(a1, n);
        printf("\n\n SUM = %d\t",sum2);
        display(a2, n);
    }
}

void divided_array(int a[], int n)
{
    int a1[n/2], a2[n/2];
    int sum1 = 0;
    int sum2 = 0; 
    int k = 0;
    int i;

    sort_array(a,n);

    a1[0] = a[n-1];
    a2[0] = a[n-2];

    for (i = n-2; i >= 2; i-=2)
    {
        sum1 += a1[k];
        sum2 += a2[k];
        k += 1;
        if (sum1 > sum2)
        {
            a1[k] = a[i - 2];
            a2[k] = a[i - 1];
        }
        else
        {
            a1[k] = a[i - 1];
            a2[k] = a[i - 2];
        }
    }

    sum1 += a1[k];
    sum2 += a2[k];

    if (sum2 > sum1)
       balance(sum2, sum1, a2, a1, k+1);
    else
       balance(sum1, sum2, a1, a2, k+1);
}

I did not implement the function sort_array.
Better to use heap sort.

 95 135 68 11 84 26 66 139 118 116 65 18

 SUM = 469        135  118  95  84  26  11

 SUM = 472        139  116  68  66  65  18
=========================================================
 95 145 77 34 169 79 35 67 149 33 166 77

 SUM = 561        169  149  95  79  35  34

 SUM = 565        166  145  77  77  67  33
=========================================================
 95 21 80 131 6 58 18 139 159 89 81 11

 SUM = 441        139  131  81  58  21  11

 SUM = 447        159  95  89  80  18  6
=========================================================
 67 21 80 131 82 58 18 58 159 89 81 11

 SUM = 427        159  89  82  58  21  18

 SUM = 428        131  81  80  67  58  11

Comments

Thanks in advanced If some one can reduce the complexity.

Answer 2

first find out the total of all the given numbers.. lets say it's total_sum.. then create two new arrays.. lets say A1 and A2 .. start putting elements in the first array A1 until sum of all the elements of A1>total_sum/2; then put rest numbers into A2.. then A1 and A2 will be the two subsets of minimum difference

Comments

:) Good idea
Please code it and tell complexity :)

---

package poc.random;

import java.util.Arrays;

public class Example {

    public static void main(String[] args) {
       
    //    int arr[] = {10,5,12,6,3,8};
    //    int arr[] = {21,2,12,3,5,9};
        int arr[]= {95, 135, 68, 11, 84, 26, 66, 139, 118, 116, 65, 18};
    //    int arr[]= {67, 21, 80, 131, 82, 58, 18, 58, 159, 89, 81, 11};
    //    int arr[]= {5, 21, 80, 131, 6, 58, 18, 139, 159, 89, 81, 11};
    //    int arr[]= {95, 145, 77, 34, 169, 79, 35, 67, 149, 33, 166, 77};
        int subArr1[]= new int[arr.length/2];
        int subArr2[]= new int[arr.length/2];
        subArr1[0] = arr[0];
        subArr2[0] = arr[1];
        subArr1= Arrays.copyOfRange(arr, 0, arr.length/2);
        subArr2= Arrays.copyOfRange(arr, arr.length/2,arr.length);
        int sum1=0;
        int sum2=0;
        int diffSum;
       
        for (int i = 0; i < arr.length/2; i++) {
            sum1=sum1 + subArr1[i];
            sum2=sum2 + subArr2[i];
        }
        diffSum= Math.abs(sum1- sum2);
        int temp=0;
       
        for (int i = 0; i < arr.length/2; i++) {
           
            for (int j = 0; j < subArr2.length; j++) {
           
                if(sum1 > sum2){
                     if(subArr1[i] >subArr2[j]){
                         
                         sum1=sum1- subArr1[i] + subArr2[j];
                         sum2=sum2- subArr2[j] + subArr1[i];
                         if(diffSum >= Math.abs(sum1- sum2)){
                             diffSum= Math.abs(sum1- sum2);
                             temp= subArr1[i];
                             subArr1[i]= subArr2[j];
                             subArr2[j]= temp;
                        }else{
                             sum1=sum1- subArr2[j] + subArr1[i];
                             sum2=sum2- subArr1[i] + subArr2[j];
                         }
                         
                         
                     }
                   
                }else if (sum1 < sum2){
                   
                    if(subArr1[i]  < subArr2[j]){

                         sum1=sum1- subArr1[i] + subArr2[j];
                         sum2=sum2- subArr2[j] + subArr1[i];
                         if(diffSum >= Math.abs(sum1- sum2)){
                             diffSum= Math.abs(sum1- sum2);
                             temp= subArr1[i];
                             subArr1[i]= subArr2[j];
                             subArr2[j]= temp;
                        }else{
                             sum1=sum1- subArr2[j] + subArr1[i];
                             sum2=sum2- subArr1[i] + subArr2[j];
                         }
                         
                    }
                }
                else {
                    break;
                }
               
            }
           
        }
        for (int i = 0; i < subArr1.length; i++) {
            System.out.print(" "+subArr1[i]);
        }
        System.out.print("   sum is "+ sum1);
       
        System.out.print("        second array");
        for (int i = 0; i < subArr2.length; i++) {
            System.out.print(" "+subArr2[i]);
        }
        System.out.print("   sum is "+ sum2);
        System.out.println("  difference is "+ diffSum);
    }
}