Risolvi la partizione-in-tre set nel tempo pseudo-polinomiale

Question

Permettere Partizione-in-tre set essere definito come segue:

Ingresso: Interi positivi $ a_1, ..., a_n $

Problema: Ci sono tre set disgiunti a coppie $ I, j, k sottoseteq {1, ..., n } $ insieme a $ I CUP J CUP K = {1, ..., n } $, affinché $ sum_ {i in i} {a_i} = sum_ {j in j} {a_j} = sum_ {k in k} {a_k} $?

È facile da mostrare, che la partizione-in-tre set è NP-completa facendo una partizione di riduzione del tempo polinomiale $ le $ Partizione-in-tre set.

Come partizione può essere risolto Nel tempo pseudo-polinomiale con programmazione dinamica, dovrebbe esserci un modo per risolvere la partizione-in-tre set nel tempo pseudo-polinomiale. Esiste una soluzione per adattare l'algoritmo pseudo-polinomiale per questo problema?