Dada uma lista de números inteirosl, como posso particioná-lo em 2 listasa eb de tal modo qued(a,b) = abs(sum(a) - sum(b)) é mínimo. Sei que o problema é NP-completo, então estou procurando um algoritmo de tempo pseudo-polinomial, ou seja,O(c*n) Ondec = sum(l map abs). Eu olheiWikipedia mas o algoritmo existe para particioná-lo em metades exatas, que é um caso especial do que estou procurando ...

EDIT: Para esclarecer, estou procurando as partições exatasa eb e não apenas a diferença mínima resultanted(a, b)

Para generalizar, o que é um algoritmo de tempo pseudo-polinomial para particionar uma lista den números emk gruposg1, g2 ...gk de tal modo que(max(S) - min(S)).abs é o menor possível, ondeS = [sum(g1), sum(g2), ... sum(gk)]