# In how many ways can a set of integers be summed to a target integer?

Given a set $X$ of $m$ distinct positive integers $X = \{x_1,x_2,\dots,x_m\}$ and a positive integer $N$, in how many ways can $N$ be expressed as a sum $N = \sum_i y_i$ with $y_i\in X$? The order of the sum does not matter.

• Seems like more information on the $x_i$ would be needed. Did you make any progress on this? – Joffan Jun 15 '18 at 23:56
• That is a partition of $N$, with parts belonging to the set $X$, and in general does not have a close form. – G Cab Jun 16 '18 at 0:02
• You might be interested in the "subset sum problem". en.wikipedia.org/wiki/Subset_sum_problem – awkward Jun 16 '18 at 15:05

## 2 Answers

Without further information on the nature of the $x_i$, I can only offer $$\sum_{S\subseteq X}\large\delta_{(\sum_S s_i)(N)}$$ where $\delta_{ij}$ is the Kronecker delta. Basically though this is just re-stating the problem.

There might be more scope for useful description for special forms like $X=\{1,2,3,\ldots,m\}$ but even then because the number of elements in the subset is variable, there's no clean transformation to another partition.

A recursive definition of a function which returns the number of those partitions might look like this: \begin{align} f(N, X) &= 0 \quad (N \le 0) \\ f(N, \emptyset) &= 0 \\ f(N, \{ x \} \cup X) &= \delta[N–x] + f(N-x, X) + f(N, X) \end{align} where I used the Dirac delta in discrete / DSP notation: $$\delta[n] = \begin{cases} 1 & \text{if } n=0 \\ 0 & \text{if } n\in \mathbb{Z}\setminus\{0\} \end{cases}$$ Update: I assumed the elements of $X$ being used only once in the sum.

• Note that a member $x\in X$ can appear multiple times in the sum. But writing a recursion is seems like a good idea. The choice can be whether $x$ is chosen at least once, or not. This leads to: $f(N, X\cup \{x\}) = f(N - x, X\cup \{x\}) + f(N, X)$ – becko Jun 16 '18 at 9:37
• Also you can define $f(0, X) = 1$ instead of 0. Since the empty set is a subset of $X$. – becko Jun 16 '18 at 9:41
• Maybe the recursion can be solved for special cases of $X$? – becko Jun 16 '18 at 9:41
• I have to rethink the problem for multiple use in the sum. – mvw Jun 16 '18 at 16:14