algorithm - 子集和的变体

Question

给定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) 的复杂性在这个问题上？

Answer 1

关于如何利用 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) 的复杂度(当然，可能存在一些我确实错过的微妙之处)