I have a number n, and I have to split it into k numbers, so that all k numbers are different, the sum of k numbers is n, and k is the maximum. Example, if n is 9, then the answer should be 1,2,6. If n is 15, then the answer should be 1,2,3,4,5.
This is what I tried -
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);
}
}
Initially, k = n and l = 1. The resulting numbers are stored in s. This solution, although it returns the number n as the sum of k different numbers, but it is not an optimal solution (k is not maximal). An example output for n = 15 is 1,2,4,8. What changes need to be made to get the right result?
source
share