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

Question

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.

Answer 1

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.

Answer 2

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.