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?