CODEWITHSUNDEEP
carraysalgorithm
Behzad Hassani
Behzad Hassani

Reputation: 2139

Minimum Complexity of two lists element summation comparison

I have a question in algorithm design about arrays, which should be implement in C language. Suppose that we have an array which has n elements. For simplicity n is power of '2' like 1, 2, 4, 8, 16 , etc. I want to separate this to 2 parts with (n/2) elements. Condition of separating is lowest absolute difference between sum of all elements in two arrays for example if I have this array (9,2,5,3,6,1,4,7) it will be separate to these arrays (9,5,1,3) and (6,7,4,2) . summation of first array's elements is 18 and the summation of second array's elements is 19 and the difference is 1 and these two arrays are the answer but two arrays like (9,5,4,2) and (7,6,3,1) isn't the answer because the difference of element summation is 4 and we have found 1 . so 4 isn't the minimum difference. How to solve this? Thank you.

Upvotes: 0

Views: 136

Answers (1)

amit
amit

Reputation: 178441

This is the Partition Problem, which is unfortunately NP-Hard.

However, since your numbers are integers, if they are relatively low, there is a pseudo polynomial O(W*n^2) solution using Dynamic Programming (where W is sum of all elements).

The idea is to create the DP matrix of size (W/2+1)*(n+1)*(n/2+1), based on the following recursive formula:

D(0,i,0) = true
D(0,i,k) = false     k != 0
D(x,i,k) = false     x < 0
D(x,0,k) = false     x > 0
D(x,i,0) = false     x > 0
D(x,i,k) = D(x,i-1,k) OR D(x-arr[i], i-1,k-1)

The above gives a 3d matrix, where each entry D(x,i,k) says if there is a subset containing exactly k elements, that sums to x, and uses the first i elements as candidates.

Once you have this matrix, you just need to find the highest x (that is smaller than SUM/2) such that D(x,n,n/2) = true

Later, you can get the relevant subset by going back on the table and "retracing" your choices at each step. This thread deals with how it is done on a very similar problem.

For small sets, there is also the alternative of a naive brute force solution, which basically splits the array to all possible halves ((2n)!/(n!*n!) of those), and picks the best one out of them.

Upvotes: 5

Related Questions