Задача о рюкзаке, даже о двух :)
Заводите массив M[0..S/3,0..S/3] (можно битовый, но лучше побольше - чтобы хранить обратные ссылки). В нём будут отмечены элементы M[a,b], такие, что из уже просмотренных элементов текущего набора можно выбрать непересекающиеся подмножества с суммами a и b.
Когда приходит очередной элемент x - выполняете M[a,b]=M[a,b] | M[a-x,b] | M[a,b-x] для всех a,b начиная с конца (с больших a,b). Если при этом 0 сменился на 1 - помечаете в массиве обратных ссылок, из какого элемента вы сюда попали.
Сложность - O(n*S^2). Можно ли сделать лучше, не знаю.
Вот вариант кода - но он печатает только два множества. Как напечатать третье, разберётесь.
spoilerstatic void Main(string[] args) {
int[] dat=Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
int S=0;
foreach(int x in dat) S+=x;
if(S%3!=0) {
Console.WriteLine("-1"); return;
}
S/=3;
int[,] M=new int[S+1,S+1];
M[0,0]=-1;
foreach(int x in dat) {
for(int a=S;a>=0;a--) {
for(int b=S;b>=0;b--) {
if(M[a,b]==0) {
if(a>=x && M[a-x,b]!=0) M[a,b]=x; // back by set1
else if(b>=x && M[a,b-x]!=0) M[a,b]=-x; // back by set2
}
}
}
}
if(M[S,S]==0) {
Console.WriteLine("-1"); return;
}
int u=S,v=S;
string res1="",res2="";
while(u!=0 || v!=0) {
if(M[u,v]>0) {
res1+=" "+M[u,v]; u-=M[u,v];
} else {
res2+=" "+(-M[u,v]); v+=M[u,v];
}
}
Console.WriteLine(res1);
Console.WriteLine(res2);
}
