2
$\begingroup$

Problem

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$.

Question

This problem came from evaluating some scheduling algorithms that I am interested in optimizing for some small home grown useless embedded system I am playing with. My problem is that I do not know if this problem is NP-Complete like the K-Sum problem. I am guessing it might be but it has been a while since I have dealt with proofs pertaining to NP problems. I remember something with SAT, but looking around did not jog any memories (at least any good ones).

How might I prove it is or is not NP-Complete?

$\endgroup$
7
  • $\begingroup$ Are you aware the subset sum problem is NP-complete? $\endgroup$
    – John L.
    Jan 23, 2019 at 18:51
  • $\begingroup$ @Apass.Jack Yes, I am aware of this. And k-sum is essentially the subset sum problem, correct? $\endgroup$
    – tkellehe
    Jan 23, 2019 at 19:26
  • $\begingroup$ Is that sufficient enough to prove that this problem is NP-Complete? I thought it involved more gymnastics than that? $\endgroup$
    – tkellehe
    Jan 23, 2019 at 19:57
  • $\begingroup$ So, essentially all I have to say is that the range of numbers is my set for the k-sum problem and it is now NP-Complete? $\endgroup$
    – tkellehe
    Jan 23, 2019 at 20:09
  • $\begingroup$ Wait. I might not be careful enough. "Given a range of numbers $[a,\cdots,b]$", do you mean a list of number $a_1, a_2, \cdots, c_n$? When we compute the time-complexity, is it in terms of $n$ or in terms of $k$ and $n$? $\endgroup$
    – John L.
    Jan 23, 2019 at 20:29

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for the exercises.This makes a lot more sense now:) $\endgroup$
    – tkellehe
    Jan 23, 2019 at 21:47
  • 3
    $\begingroup$ Depending on how you interpret "find a subset of sum k", you can do this in constant time. Not if you insist on k numbers, but if you allow something like "the numbers from 12 to 17, plus the numbers from 19 to 24" or "the numbers from 12 to 24 except 18" as the solution. $\endgroup$
    – gnasher729
    Jan 24, 2019 at 1:15
0
$\begingroup$

I suspect a polynomial-time algorithm exists. WLOG, you can assume $a=0$ (subtract $a$ from all numbers in the range, and subtract $ak$ from $s$). Then the problem becomes: given a range $\{0,\dots,b\}$, find a subset of size $k$ that sums to $s$. If you allow a multiset, it is easy to come up with a polynomial-time algorithm; take $k-1$ copies of $\lfloor s/(k-1) \rfloor$ and one copy of $s - \lfloor s/(k-1) \rfloor$. I suspect similar ideas can probably be applied to find a set as well (i.e., to avoid repeats). I suggest you spend some time working out the details to see.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.