给定3正整数 n, k, and sum , 准确找到 k不同元素的数量 a_i , 其中
a_i \in S, 1 <= i <= k, and a_i \neq a_j for i \neq j
和 S是集合
S = {1, 2, 3, ..., n}
这样
\sum_{i=1}^{k}{a_i} = sum
由于指数复杂性，我不想使用蛮力(检查所有可能的组合)来解决问题。有人可以给我一个解决这个问题的另一种方法的提示吗？另外，我们如何利用集合 S 的事实排序了吗？
是否可能有 O(k) 的复杂性在这个问题上？
最佳答案
关于如何利用 1..n 设置属性的想法:
从a开始的自然行的k个连续成员之和为
sum = k*(2*a + (k-1))/2
为了获得关于所需s的子序列的总和，我们可以解决
a >= s/k - k/2 + 1/2
or
a <= s/k - k/2 + 1/2
比较 s 和 sum 值并进行更正。
例如，s=173，n=40，k=5，我们可以找到
a <= 173/5 - 5/2 + 1/2 = 32.6
对于起始编号 32，我们有序列 32,33,34,35,36 和 sum = 170，对于 3 的校正，我们只需将 36 更改为 39 ，或 34,35,36 和 35,36,37 等等。
似乎使用这种方法我们得到了 O(1) 的复杂度(当然，可能存在一些我确实错过的微妙之处)
关于algorithm - 子集和的变体，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39554616/