it's a subset sum problem with the targetted sum equal to half of the sum of elements in the array. It can be solved usin DP.

View Allnum of num

2 Answers

▲

0

▼

it's a subset sum problem with the targetted sum equal to half of the sum of elements in the array. It can be solved usin DP.

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

Solved by factoring sum of entire set and finding all candidate numbers which sums up to that factor. That is if the set sum = 15. Factorize 15 such as 1+14, 2+13, etc. And find all the candidates in the set which sums up to 1 and 14(and so on). Then subgroup them. Then follow up was how to handle negative values, what if values are largely distributed like {-1M1, -1, 0, 1M} The above method performs miserably. One solution I gave was to reduce numbers by orders of magnitude. That is above set is equivalent to {-11, -1, 0, 10} and while finding out factors of sum, go from -x to +y where x being most negative and y being most positive value in a given set.