spalte eine Zahl n als Summe von k verschiedenen Zahlen

Question

Ich habe eine Nummer n und ich muss es in k Zahlen so teilen, dass alle k Zahlen sind unterschiedlich, die Summe der k Zahlen ist gleich n und k ist maximal. Beispiel wenn n 9 ist, dann sollte die Antwort 1,2,6 sein. Wenn n 15 ist, dann sollte die Antwort 1,2,3,4,5 sein.
Dies ist, was ich versucht habe -

void findNum(int l, int k, vector<int>& s) 
{ 
    if (k <= 2 * l) { 
     s.push_back(k); 
     return; 
    } 
    else if (l == 1) { 
     s.push_back(l); 
     findNum(l + 1, k - 1, s); 
    } 
    else if(l == 2) { 
     s.push_back(l); 
     findNum(l + 2, k - 2, s); 
    } 
    else{ 
     s.push_back(l); 
     findNum(l + 1, k - l, s); 
    } 

} 

Zunächst k = n und l = 1. Die resultierenden Zahlen in s gespeichert sind. Diese Lösung gibt zwar die Zahl n als eine Summe von k eindeutigen Zahlen zurück, aber es ist nicht die optimale Lösung (k ist nicht maximal). Beispielausgabe für n = 15 ist 1,2,4,8. Welche Änderungen sollten vorgenommen werden, um das richtige Ergebnis zu erhalten?

Answer 1

Greedy-Algorithmus funktioniert für dieses Problem. Beginnen Sie einfach von 1 bis m summieren, so dass sum(1...m) <= n. Sobald der Wert überschritten wird, fügen Sie den Überschuss zu hinzu. Zahlen von 1 bis m | m-1 werden die Antwort sein.

z.

18 
1+2+3+4+5 < 18 
+6 = 21 > 18 
So, answer: 1+2+3+4+(5+6-(21-18)) 

28 
1+2+3+4+5+6+7 = 28 
So, answer: 1+2+3+4+5+6+7 

Pseudocode (in konstanter Zeit, Komplexität O (1))

Find k such that, m * (m+1) > 2 * n 
Number of terms = m-1 
Terms: 1,2,3...m-2,(m-1 + m - (sum(1...m) - n))