Андрей Ежгуров

Например, потому, что дикое количество выделений / освобождений памяти. А это всегда не быстро.

А ещё утечки памяти: add(add(P5, P6, k), T1, k); - память, выделенная в add(P5, P6, k), не освобождается.

Условия слишком переусложнённые. Можно же проще:

if (abs(a) + abs(b) + abs(c) + abs(d) == 0) {
  cout << -1;
  return 0;
}
if (d != 0) { poisk(d, a, b, c, d); } else { s.push_back(0); }
if (c != 0) { poisk(c, a, b, c, d); } 
if (b != 0) { poisk(b, a, b, c, d); } 
if (a != 0) { poisk(a, a, b, c, d); }

Да, будут лишние циклы, но ничего не пропустили и ничего не перепутали.