1
$\begingroup$

There is a number $n(\gt 1)$ and a finite set $S=\{1,2,...,r\}$. Here $n\ge r$. How do I form $n$ as the sum of exactly $k$ distinct elements of $S$ where $k \ge 1$, or know that it's impossible to do so?

$\endgroup$

3 Answers 3

1
$\begingroup$

This problem is reminiscent of Kakuro, the logic puzzle where distinct digits (i.e. $r=9$) have to be filled into entries of a fixed length $k$ such that they have a given sum $n$.

For a given $r$ and $k\le r$:

  • The smallest $n$ possible is $T_k=\frac{k(k+1)}2$, and is the result of choosing the $k$ smallest elements of $S$.
  • The largest $n$ possible is $k(r+1)-T_k$, arising from choosing the $k$ largest elements of $S$.
  • All numbers between these two bounds are achievable.

Taking $r=9$ and $k=4$ as an example, the smallest $n$ that can be formed is $T_4=10$, corresponding to a Kakuro line with 1234 in it. The largest $n$ is $4×10-T_4=30$, corresponding to a line with 6789. If $n=20$, I could achieve it in many ways like 2567 and 1379.

$\endgroup$
1
  • $\begingroup$ Nice! :) Assume n is between those two bounds. Any idea on how I can possibly generate such a set of numbers with sum equal to n? $\endgroup$ Aug 28, 2016 at 11:09
0
$\begingroup$

Okay I figured out an algorithm to do this! Don't know how useful it might be if used to generate this decomposition by hand. But it's a nice method nonetheless and will work well in a computer program. Let $p$ be such that $1\leq p\le r-k+1$. Now we select the $p$ such that the sum of the $k$ consecutive elements starting from $p$ is as close to $n$ as possible(call this value of $p$ as $p_0$ and the respective sum $S$ as $S_0$). That is, we select the maximum $p$ such that

$$S=\frac{(p+k)(p+k-1)}{2}-\frac{p(p-1)}{2}\le n$$

In a computer program, $p_0$ can be found using Binary search in logarithmic time. Now we will distribute the remaining $d=n-S_0$ among the numbers $A=\{p_0,p_0+1,p_0+2,...,p_0+k-1\}$ with the following algorithm.

Denote the $i$ th element of $A$ as $A_i$. Starting from $A_k$ and considering each element until you reach $A_1$, increase each $A_i$ until it reaches its upperbound or the sum of all the increments so far reaches $d$. The upperbound of $A_k$ is $r$ and of all the other $A_i$ where $1 \le i \le k-1$ is $A_{i+1}$. The algorithm terminates when the cumulative sum of all increments reaches $d$.

Now, the elements remaining in $A$ will give you the desired decomposition of $n$. Of course, as Parcly Taxel has mentioned in his answer, we have to check whether $$\frac{k(k+1)}{2} \le n \le k(r+1)-\frac{k(k+1)}{2} $$

before proceeding with the above approach. If not, there is no valid decomposition under the given constraints.

$\endgroup$
0
$\begingroup$

There's no known easy way (for a technical meaning of "easy") and there's a million dollar prize for finding one.

This is a variant on the subset sum problem, which is NP complete. If you don't know any complexity theory then this space is too small to give a proper explanation of what that means, but the intuition is that the amount of work required is probably exponential in the size of the problem (and if it turns out to be polynomial in the size of the problem then thousands of other well-known problems are suddenly easier than was previously believed).

The standard subset sum problem doesn't fix $k$, but if this variant could be solved with polynomial effort then running one instance of it for each $1 \le k \le n$ would give a polynomial algorithm for the standard variant.

Note that this doesn't mean that the heuristic in your answer doesn't work well in practice, but it does mean that there are going to be some problem instances on which it works badly.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .