divide list in two parts that their sum closest to each other

This is a hard algorithms problem that :

Divide the list in 2 parts (sum) that their sum closest to (most) each other

list length is 1 <= n <= 100 and their(numbers) weights 1<=w<=250 given in the question.

For example : 23 65 134 32 95 123 34

1.sum = 256

2.sum = 250

1.list = 1 2 3 7

2.list = 4 5 6

I have an algorithm but it didn't work for all inputs.

1. init. lists list1 = [], list2 = []
2. Sort elements (given list) [23 32 34 65 95 123 134]
3. pop last one (max one)
4. insert to the list which differs less

Implementation : list1 = [], list2 = []

1. select 134 insert list1. list1 = [134]
2. select 123 insert list2. because if you insert to the list1 the difference getting bigger
   3. select 95 and insert list2 . because sum(list2) + 95 - sum(list1) is less.

and so on...

The problem is NPC, but there is a pseudo polynomial algorithm for it, this is a 2-Partition problem, you can follow the way of pseudo polynomial time algorithm for sub set sum problem to solve this. If the input size is related polynomially to input values, then this can be done in polynomial time.

In your case (weights < 250) it's polynomial (because weight <= 250 n => sums <= 250 n^2).

Let Sum = sum of weights, we have to create two dimensional array A, then construct A, Column by Column

A[i,j] = true if (j == weight[i] or j - weight[i] = weight[k] (k is in list)).

The creation of array with this algorithm takes O(n^2 * sum/2).

At last we should find most valuable column which has true value.

Here is an example:

items:{0,1,2,3} weights:{4,7,2,8} => sum = 21 sum/2 = 10

items/weights 0|  1  | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10    
  --------------------------------------------------------- 
  |0             |  0  | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0
  |1             |  0  | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0
  |2             |  0  | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1
  |3             |  0  | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1

So because a[10, 2] == true the partition is 10, 11

This is an algorithm I found here and edited a little bit to solve your problem:

bool partition( vector< int > C ) {
 // compute the total sum
 int n = C.size();
 int N = 0;
 for( int i = 0; i < n; i++ ) N += C[i];
 // initialize the table 
 T[0] = true;
 for( int i = 1; i <= N; i++ ) T[i] = false;
 // process the numbers one by one
 for( int i = 0; i < n; i++ )
  for( int j = N - C[i]; j >= 0; j--)
   if( T[j] ) T[j + C[i]] = true;

 for(int i = N/2;i>=0;i--)
    if (T[i])
      return i;
 return 0;
}

I just returned first T[i] which is true instead of returning T[N/2] (in max to min order).

Finding the path which gives this value is not hard.