разделил число n на сумму k различных чисел

Question

У меня есть число n, и я должен разбить его на k чисел так, чтобы все 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); 
    } 

} 

Первоначально к = п и л = 1. Полученные числа хранятся в с. Это решение, хотя и возвращает число 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))