@arun..
Couple of questions need to be clarified :
1) Are all the numbers given in the unsorted array +ive integers.. ?
2) By 2 equal arrays do you mean that both the arrays should be of size N/2
(where N is even) .. ?
If the above assumptions are true then we can use the following recurrence
to solve the problem:
/* I have excluded the base condition initializations..*/
F(i, j, k) = ( (i > j) ? F(i-1,j, k) : 0 ) || F( i-1, j-1, k - v[i] )
Only those values of F would be calculated for which the condition i>=j
holds true..
Here,
v - unsorted array..
i - sub-array of first i elements of v
j - no. of elements picked out of the first i elements
k - the sum obtained by picking j elements out of the first i element
subarray..
Calculate all the values from F(0,0,0) --> F(N, N/2, S) ( for all F(i, j,
k) 's where i>=j )
where S = (sum of the unsorted array) / 2 ...
F(i,j,k) will hold only one of the either 2 values :
0 - not possible to make a sum of K for (i, j) pick
1 - possible to make a sum of K for (i, j) pick..
Once all the values have been calculated we have to pick the max { R }
for which F(N, N/2, R) = 1, where 0 <= R <= S
Thereafter the min difference of 2 equal arrays would be:
(Sum of the unsorted array) - 2*R
On Wednesday, 7 November 2012 19:43:12 UTC+5:30, Arun wrote:
>
> Given an unsorted array, how to divide them into two equal arrays whose
> difference of sum is minimum.
--
