CareerCup

This boils down combination problem, try nCn/2 combinations and on each output, just compare the diff with the desired result(it is array total/2) if it's closest to it then this is one group.

I know I missed the ordering, but that can be handled it's not a big deal.

In this question, it's a matter of establishing your if's in the correct order. The primary constraint is that the number of boxes must be even and keep relative order(or within 1 of each other). The weight is a secondary consideration. So to complete the algorithm establish two lists and cycle through the boxes one a time and:

1. compare the size of list1 and list2. If list1.size() > list2.size() add to list 1 and go to next box(or list2.size() > list1.size() add to list 2 and go to next box).
2. if the lists are the same size compare weights of the lists. Add the box to the list with the lowest weight.

This is a greedy approach that operates in O(n) time and by inserting the items to the same point of your list each time, you maintain the ordered criteria. Note that you can also replace the list with a Queue if you want to enforce a FIFO constraint. Space complexity will be O(n) additional space for the two lists.

public void sortBoxes(Box[] boxes){
	LinkedList set1 = new LinkedList();
	LinkedList set2 = new LinkedList();
	
	int weight1 = 0;
	int weight2 = 0;
	
	for(int i = 0; i < boxes.length; i++){
		if(set1.size() < set2.size()){
			set1.add(box[i]);
			weight1 += box[i].weight;
			continue;
		}
		
		if(set2.size() < set1.size()){
			set2.add(box[i]);
			weight2 += box[i].weight;
			continue;
		}
		
		if(weight1 <= weight2){
			set1.add(box[i]);
		}
		else{
			set2.add(box[i]);
		}
	}
}

As far as I know, It's a NP-complete problem.

A good aproximation can be done like this.
first sort the array in second one, keep the position of each box from the original array.
(the sorted array contains the whieght and the original position of each box (pos)).

you need two arrays first and secnd and the total firstSum and secondSum.
if n is odd:
add the first box from the sorted array to first array in position (pos+1)/2. add its weight to the firstSum.

if n is even start here.

now distribute recursivly 4 boxes to the two arrays. (two from the end sorted array and two from the start).
if firstSum > secondSum then
{ secondArr[pos/2] = a[end] secondSum += a[end]}
{ firstArr[pos/2] = a[end-1] firstSum += a[end-1].}
else vice versa
if firstSum > secondSum then
{ firstArr[pos/2] = a[start] }
{ secondArr[pos/2] = a[start+1] }
else vice versa

now call recursively to function with start+2 and end-2.

1)take the total sum of the array and divide it by two.
2)divide the array into two equal parts as said.
3) now each two parts should be as close as possible to the total sum/2.
4)consider the first part of array.
5)pick the first element from the array and subtract it from sum/2 say it comes as y..
6)now find the closest element to the y from the entire array.
7)go on doing the same till you reach the sum/2.