C/C++ - Ottimizzazione codice partizionamento intero

Salve a tutti.

Qualche tempo fa un mio prof ci ha dato, come esercizio da fare a casa, la realizzazione di una funzione di partizione di un numero date k cifre, che fosse, in aggiunta, abbastanza efficiente da non fare affaticare la memoria nel calcolo delle varie sequenze; le partizioni di un numero, come ben saprete, sono tutte le combinazioni possibili di k cifre tali che la loro somma è uguale al numero stesso, ad esempio:

n=6
k=3

Combinazioni possibili:
{4,1,1}
{1,4,1}
{1,1,4}
{3,2,1}
{3,1,2}
{2,1,3}
{2,3,1}
{1,2,3}
{1,3,2}
{2,2,2}

Ovviamente ho già elaborato una soluzione algoritmica in C++, che è la seguente:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int somma(vector<unsigned> p)
{
	int s=0;
	
	for (int i=1; i<p.size(); i++)
	{
		s+=p[i];
	}
	
	return s;
}

void genera_permutazioni(unsigned n,unsigned amici)
{
	vector<unsigned> p(amici,1);
	p[0]=(n-amici+1);
	
	int tmp=0;
	
	while (true)// PEZZO DI CODICE ERRATO PER SEGMENTATION FAULT---> SI OCCUPA DI PARTIZIONARE UN INTERO 
	{	
		do
		{
			for (int i=0; i<amici; i++)
			{
				cout<<p[i]<<" ";
			}
			cout<<endl;
		}while(prev_permutation(p.begin(),p.end()));
		
		for (int i=1; i<amici; i++)
		{
			if (p[i]<p[0]-1)
			{
				tmp=i;
				break;
			}
		}
			
		if (tmp==0)
		{
			return;
		}
			
		for (int i=1; i<=tmp; i++)
		{
			p[i]=p[tmp]+1;
		}
			
		p[0]=(n-somma(p));
			
		tmp=0;
	}
}

int main()
{
	unsigned n,amici;

	cin>>n>>amici;
		
	genera_permutazioni(n,amici);
	
	return 0;
}

In cui, passando i parametri "n" ed "amici" alla funzione "genera_permutazioni", per ogni partizione di base effettuo la permutazione, generando tutte le possibili combinazioni.
Ovviamente il problema è dietro l'angolo: per numeri troppo grandi (orientativamente da 15 in su), il programma ci mette fin troppo ad eseguire le istruzioni, portandomi ad un segmentation_fault per la troppa memoria usata.

Avevo già cercato una soluzione in merito, provando l'approccio con la programmazione dinamica (non andato a buon fine) e col backtracking (valido ma sempre dispendioso in termini di memoria); alla luce delle considerazioni fatte, sapreste indicarmi una soluzione riguardante l'ottimizzazione del calcolo delle partizioni di numeri abbastanza grandi? Ci sto faticando da quasi un mese ma sembro non approdare da nessuna parte

ciao, al momento sono impegnato per scrivere un pò di codice e conosco poco il c++,
comunque io partirei da un ragionamento semplice (ma non so se porta a miglioramenti o meno...).
dato il tuo esempio


n=6
k=3

Combinazioni possibili:
{4,1,1}
{1,4,1}
{1,1,4}
{3,2,1}
{3,1,2}
{2,1,3}
{2,3,1}
{1,2,3}
{1,3,2}
{2,2,2}

Le reali combinazioni "univoche" che devi trovare sono:

{4,1,1}

{3,2,1}

{2,2,2}

da esse puoi trovarti le altre, basta scambiare di posto i numeri:

ad esempio:

A,B,C con avremo:

A,B,C
A,C,B
B,A,C
B,C,A
C,A,B
C,B,A

in caso di A=B o A=C o B=C basta eliminare gli "scambi di queste lettere"
Se A=B=C .. eviti tutti gli scambi.

Per trovare le combinazioni "univoche"
Parti da p[0]=n-K+1 (ed il resto tutti 1) come hai fatto tu, poi diminuisci di 1 K fino ad arrivare a p[0]=n/K ed aumenta p[1] di 1, dal primo p[0] (p[0]=n-K+1) abbassi di 2 ed una volta ne aggiungi 2 a p[1], poi aggiungi questo '2' agli indici successivi
p[1]+=1; P[2]+=1;
La 3° volta
p[1]+=3;
p[1]+=2; p[2]+=1;
p[1]+=1; p[2]+=1; p[3]+=1;
ecc. fino ad arrivare a p[0]=n/K

il resto delle soluzioni si ottengono scambiando di ordine i membri delle soluzioni "univoche"
Comunque sia... il calcolo sarà sempre abbastanza elevato per numeri alti...