To complete the answer, you first need to compute C(m,n) as [email protected] said and then look for the closest m to s/2 as sharad kumar said.
proof: you are looking for two complimentary subset with sum of m and s-m (assume m>s-m) you are looking for a reachable m, which minimize |m - (s-m)|. |m-(s-m)| = m - s +m = 2m-S = 2 (m-S/2) = 2|S/2-m| ==> so minimizing | S/2-m| is equvalent to minimizing the difference of two complimentary subsets. On Sep 5, 5:54 pm, [email protected] wrote: > This is a classic DP problem. > Assuming we have an integer array a[1...N]. We define C(m,n) as below: > 1. If we can find a subset of a[1...m] whose sum is n, then C(m,n)=1. > 2. Else C(m,n)=0 > Easy to find that: > C(m,n)=C(m-1,n) || C(m-1,n-a[m]). > Got it? > > Sent from my iPad > > On Sep 5, 2010, at 7:37 AM, Raj Jagvanshi <[email protected]> wrote: > > > There is an array of some no only 0-9. > > You have to divide it into two array > > such that sum of elements in each array is same. > > Eg input {1,2,3,4} output {1,4}{2,3} > > > this question of nagaroo company > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group > > athttp://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
