CareerCup

uses DP and more can be read on en.wikipedia.org/wiki/Partition_problem :

public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int arr[] = new int[n];
		int K = 0;//sum of array

		for (int i = 0; i < n; i++) {
			arr[i] = in.nextInt();
			K = K + arr[i];
		}
		
		//algorithm starts here
		int M[] = new int[K + 1];
		M[0] = 1;
		for (int i = 0; i < n; i++) {
			for (int j = K - arr[i]; j >= 0; j--) {
				if (M[j] == 1)
					M[j + arr[i]] = 1;
			}
		}
		int mindiff = Integer.MAX_VALUE;
		for (int i = 1; i <= K; i++) {
			if (M[i] == 1) {
				int s1 = i;
				int s2 = K - s1;
				if (Math.abs(s2 - s1) < mindiff)
					mindiff = Math.abs(s2 - s1);
			}
		}
		System.out.println(mindiff);
	}

try this , not tested properly

int[] a = { 1, 2, 3, 4, 5, 1 };
		int sm = 0;

		for (int i = 0; i < a.length; i++)
			sm += a[i];

		boolean[] dp = new boolean[sm + 1];
		dp[0] = true;

		for (int i = 0; i < a.length; i++) {

			for (int j = 0; j <= sm - a[i]; j++)
				if (dp[j])
					dp[j + a[i]] = true;
		}

		for (int i = sm / 2; i >= 0; i--)
			if (dp[i]) {
				System.out.printf("set 1:%d  set 2:%d\n", i, sm - i);
				break;

not tested 


int[] a = { 1, 2, 3, 4, 5, 1 };
		int sm = 0;
		for (int i = 0; i < a.length; i++)
			sm += a[i];

		boolean[] dp = new boolean[sm + 1];
		dp[0] = true;

		for (int i = 0; i < a.length; i++) {

			for (int j = 0; j <= sm - a[i]; j++)
				if (dp[j])
				dp[j + a[i]] = true;
		}

		for (int i = sm / 2; i >= 0; i--)
			if (dp[i]) {
			System.out.printf("set 1:%d  set 2:%d\n", i, sm - i);
			break;
			}

I think we can do this using backtracking. First make a note of no.of elements in the array(say 'n') and the sum of all those elements(say 'sum').

At the start of the backtracking function check if the no.of elements in temp array are equal to half of the elements in original array. If so, then calculate the sum of temp array and compare with original array sum.

Temp array sum having least difference with half of original array sum is one of the two half arrays we are looking for. The other half array will be with remaining elements of original array not included in first half array.

Here is the backtracking approach:

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
 
 
void back(int *arr,int *sol,int N,int tillnow,int sumtillnow,int remainsum,int *finalsol)
{
        static int mindiff=INT_MAX;
        int i;
        if(tillnow==N/2)
        {
                if(abs(sumtillnow-remainsum)<mindiff)
                {
                        mindiff=abs(sumtillnow-remainsum);
                        for(i=0;i<N;i++)
                                finalsol[i]=sol[i];
                }
        }
        else
        {
                for(i=0;i<N;i++)
                {
                        if(!sol[i])
                        {
                                sol[i]=1;
                                back(arr,sol,N,tillnow+1,sumtillnow+arr[i],remainsum-arr[i],finalsol);
                                sol[i]=0;
                        }
                }
        }
}
 
int main()
{
        int arr[10]={1,2,3,4,5,6,7,8,9,10},sol[10]={0},finalsol[10],i,sum=0;
        for(i=0;i<10;i++)
                sum+=arr[i];
 
        back(arr,sol,10,0,0,sum,finalsol);
 
        for(i=0;i<10;i++)
        {
                if(finalsol[i])
                        printf("%d ",arr[i]);
        }
        printf("\n");
 
        for(i=0;i<10;i++)
        {
                if(!finalsol[i])
                        printf("%d ",arr[i]);
        }
}

Hope this works:


Assumptions are
All are positive elements
We have to split into 2 equal halves

Split it into 2 equal sets
Get the sum of each set
Set diff = |Sum(SetA) - Sum(SetB)|
While diff is > 1
Begin
-- Logic is try to reduce the difference between the two sets by exhanging 2 elements every time
DiferenceInDataToBeMoved = diff / 2
Find out the 2 elements one in SetA and another in SetB with diff <= DiferenceInDataToBeMoved
If 2 such elements are found
Exchange those 2 elemnts
Else
Return the 2 sets

Set diff = |Sum(SetA) - Sum(SetB)|
End

Return the 2 sets

May be this will work
Find the sum of whole array =(s).
Now, we've to find an sub-array whose sum <= s/2 and min(s/2-sum) and must contain n elements.
One way is to create every possible sub-array(n elements) and find the min(s/2-sum) .

Let us take an array which is sorted; eg:{1,2,3,6,8,9} - 4 elements
Te difference between the two subsets will be least when the elements are alternately put into the two different lists:
For example - first take 2 nos. - 1,2 =>put 1 in SetA and 2 in SetB [SetA{1} ; SetB{2}]
Then take the next two nos. - 3,6 => put 3 in SetB and 6 in SetA[SetA{1,6}, SetB{2,3}]
Then the next 2 - 8,9 => put 8 in SetA and 9 in SetB [SetA{1,6,8}; SetB{2,3,9}]

The logic is based on the fact that the difference will be least when the two nos. with least difference between them are put into different list. Sorting will automatically take care of this aspect. Now the reason behind alternating the insertions between the two sets is to keep the balance - if you inserted the smaller of the two nos. earlier in one set, compensate with a larger of the two nos. in the next iteration.

This is a tested code, it will work for all the cases, it is based on greedy algorithm where we start from index 1 and find the element which is nearest distance from it using O(n) time, then we put both these elements as used, now we use a par array of same size and maintain left and right index, now we see that if sumleft is less than sum right we put higher of the nearest neighbour in left part of partition that way trying to balance the sum of each half.

#include <stdio.h>
#include <stdlib.h>

int A[10] = {1,2,3,4,5,6,7,8,9,10};
bool used[10]={0};
int par[10]={0};

int mod(int n) {
  if ( n>=0) return n;
  else 
  return (-n);   
    
}

int findMinDiff(int A[], bool used[], int idx, int N) {
    int min = 1000; int minIndex = -1;
    for (int i =0; i <N; i++) {
        if(i==idx) continue;
        if(used[i]==1) continue;
        int diff =  mod(A[idx]-A[i]);
        if(diff < min){
            min = diff;
            minIndex = i;
        }   
    }
    printf("minimum distance neighbour for %d is %d with index %d and %d respectively\n",A[idx],A[minIndex],idx,minIndex);
    return (minIndex);
}
int sumL(int left){
    int sum=0;
    for (int j = 0; j <left; j++){
        sum=sum+par[j];
    }   
    printf("sum left for left=%d is \n",sum);
    return(sum);
}

int sumR(int right){
    int sum=0;
    for (int j = 9; j >right; j--){
        sum=sum+par[j];   
    }
    printf("sum right for right=%d is \n",sum);   
    return (sum);
}

int min(int a, int b) {
    if ( a < b) return a;
    else 
        return b;
     
}

int max(int a, int b) {
    if ( a > b) return a;
    else 
        return b;
}    

void partitionSum(){
    int M=10;
    int left=0; int right=M-1;
    
    for ( int i =0; i <M; i++ ){
        
         if(used[i]==1) continue;
         
         int j = findMinDiff(A,used,i,M);
         used[j]=1;  used[i]=1;
         if (sumL(left) <= sumR(right)) {
             par[left++] = max(A[i],A[j]);
             par[right--] =  min(A[i],A[j]); 
                       
         }    
         else {
             par[left++] = min(A[i],A[j]);
             par[right--] =  max(A[i],A[j]);     
         }
    }          
}
    
int main(){
 partitionSum();
 for(int i =0; i <10; i++)
     printf("%d ",par[i]);
    
  for(int k=0; k <10; k++)
      printf("%d ",used[k]);
 getchar();
 return 0;   
}

This comment has been deleted.

1. Sort the array.
2. Pick odd indexed elements in the array for first set and even indexed elements for second set.

This solution will not work if arrays are not to be divided in two equal halves.