c++ - 将数字 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);
    }

}

最初 k = n 且 l = 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))