O número de soluções é enorme mesmo. Por outro lado, o número de threads que vocês criam (e portanto de memória que vocês alocam) é controlável. Aí o problema é conseguir criar um buffer que será consumido pela CPU para escrever os resultados.
Fórum