番号nをk個の別個の番号の和として分割する

Question

私は番号nを持ち、k個の番号に分けてk個の番号の合計がnに等しく、kが最大になるように分割する必要があります。例nが9の場合、答えは1,2,6でなければなりません。 nが15の場合、答えは1,2,3,4,5となるはずです。
これは私が試したものである -

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); 
    } 

} 

を最初= N及びL K = 1の結果の数をSに格納されています。この解は数nをk個の異なる数の和として返しますが、最適解ではありません（kは最大ではありません）。 n = 15の出力例は1,2,4,8です。正しい結果を得るためにはどのような変更を行う必要がありますか？

Answer 1

この問題では貪欲アルゴリズムが動作します。 1からmまでの合計を開始して、sum(1...m) <= nとします。それを超えるとすぐに、余分をm-1に加えてください。 1からm | m-1までの数字が答えになります。

例えば、

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 

擬似コード（時定数で、複雑性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))