将一个数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。应该进行哪些更改才能获得正确的结果？

- XZ6H

---

这里有什么问题 - n = 15 的输出结果是 1,2,4,8？？ - Wasi Ahmad

@WasiAhmad 8 可以分成 5 和 3，结果的总数将是 5 而不是 4。 - XZ6H

动态规划 - mangusta

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

- vish4071

---

找到满足 m * (m+1) > 2 * m 的 k 值是多少？k 在这个式子中的位置在哪里？ - user3103059

k retains its meaning, ie. no of terms. For this equation, k will finally be equal to m-1 - vish4071

Answer 2

如果 min(k) ≤ sum ≤ max(k,m)，则 sum 可以被分成 {1, ... , m} 中的 k 个项。

min(k) = 1 + 2 + .. + k = (k*(k+1))/2

max(k,m) = m + (m-1) + .. + (m-k+1) = k*m - (k*(k-1))/2

所以，您可以使用以下伪代码：

fn solve(n, k, sum) -> set or error
  s = new_set()
  for m from n down to 1:
    # will the problem be solvable if we add m to s?
    if min(k-1) <= sum-m <= max(k-1, m-1) then
      s.add(m), sum-=m, k-=1
  if s=0 and k=0 then s else error()

- mookid