-1
$\begingroup$

I was proposed (in school) to develop an approach to solve optimally the balanced partition problem. I tried the pseudo-linear algorithms but SUM is very large (~1M) and so O(S*N) cant run under available time (1000ms). I talked to the teacher and with N =< 60 he recommended the brute force (we are learning recursion). I've tried some approaches but I cant find a recursive algorithm that runs under 1 second. Its possible as some students got an solution that runs in less than 100ms.

What is an efficient recursive approach to this problem given data with this magnitude?

$\endgroup$
1
$\begingroup$

Would have been better on stackoverflow...

A pseudo-linear algorithm should run below a second with these numbers (sum ≤ 1000000, N = 60), if you represent the numbers that can be written as the sum of the first k integers using a bitmap using 64 bit integers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy