Résoudre la partition-into-trois sets en temps pseudo-polynomial

Question

Laisser Partition-into-trois sets être défini comme suivant:

Saisir: Entiers positifs $ a_1, ..., a_n $

Problème: Y a-t-il trois ensembles disjoints par paires $ I, j, k subseseq {1, ..., n } $ avec $ I cup j cup k = {1, ..., n } $, pour que $ sum_ {i in i} {a_i} = sum_ {j in j} {a_j} = sum_ {k in k} {a_k} $?

Il est facile à montrer que la partition-Into-Three sets est NP-Complete en faisant une partition de réduction en temps polynomial $ le $ Partition-into-trois sets.

Comme partage peut être résolu Dans le temps pseudo-polynomial avec une programmation dynamique, il devrait y avoir un moyen de résoudre la partition-into-trois sets en temps pseudo-polynomial. Existe-t-il une solution pour adapter l'algorithme pseudo-polynomial pour ce problème?