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.
- 2,129
- 4
- 30
- 51
-
PS, why the restriction of `n` be a power of 2? To have two subarrays of the exact same size, you just need `n` to be even, and not the much stronger assumption of it being power of 2. – amit May 14 '15 at 11:33
-
1@amit I know this buddy . but I think in the next steps it will separate it to another pieces so it needs an n in this condition – Behzad Hassani May 14 '15 at 11:35
-
Duplicate http://stackoverflow.com/questions/6597180/divide-an-array-into-two-sets-with-minimal-difference – therealprashant May 14 '15 at 12:15
-
@therealprashant Not exactly a dupe, since there is an extra restriction here on the cardinality of the two subsets (same size) – amit May 14 '15 at 17:20
-
Actually I should have said refer instead of duplicate . – therealprashant May 15 '15 at 04:58
1 Answers
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.
