Check if K-Sum Variation is NP-Complete
Nice question!


  Given a range of integers $\{a,a+1,...,b−1,b\}$, find a subset of size $k$ such that the sum is equal to $s$.


Well, this problem can be solved in $O(n)$ time, where $n$ is the number of given integers.

(Continuity of $k$-sums). Given integers $\{a,a+1,...,a+n-1\}$, an integer $k$, $1\le k\le n$ and an integer $s$, there are $k$ integers whose sum is $s$ if and only if $ka+\dfrac{(k-1)k}2\le s\le k(a+n-1)-\dfrac{(k-1)k}2$

Here is the algorithm.



Check if $ka+\dfrac{(k-1)k}2\le s\le k(a+n-1)-\dfrac{(k-1)k}2$. If not, return none.

Let $sum = s$. Let $S$ be an empty set.
For $i$ from 0 to $n-1$ do the following.


Let $temp = sum -(b - i)$. 
If  $temp\le (k-i-1)(a+n-1)-\dfrac{(k-i-2)(k-i-1)}2$,
let $sum = temp$ and insert $b-i$ into $S$. Otherwise, do nothing.
If $sum = 0$, break the loop.


Return S.



Here are a few related exercises.

Exercise 1. Prove the proposition of continuity of $k$-sums.

Exercise 2. Show the algorithm is correct.

Exercise 3. Modify the algorithm so that it will try adding the smallest number first.

Exercise 3. Modify the algorithm so that it will run in $O(k)$ time.