Finding groupings of numbers that add up to values in a target set

Question

I am wondering if there is an efficient way to partition a set of numbers into subsets that sum to values in a set of target values.

Specifically, let's assume that we are given $k$ distinct values (i.e., no repeats) in one set $S$ and $m$ values in another set $T$ where repeats are possible, where $m < k$. The goal is to find a set of subsets of $S$ that sum to the elements in $T$, where we must use up all of the elements of $T$ and $S$.

I think this is easiest understood with a concrete example:

$k = 6$, $m = 3$, $T = \{37, 44, 55\}$, $S = \{4, 5, 9, 30, 37, 51\}$.

The correct answer should be $\{\{37\}, \{4, 51\}, \{5, 9, 30\} \}$ since $37 \in T$, $4 + 51 = 55 \in T$, and $5 + 9 + 30 = 44 \in T$.

My approach: Go through all integer partitions of $k$ of length $m$. Here, we need to partition 6 into a sum of 3 numbers, of which there are 3 such partitions: $\{1, 1, 4\}, \{2, 2, 2\}$, and $\{1, 2, 3\}$. Then, go through each partition and see if it works given the values in $S$ and $T$. For $\{1, 1, 4\}$, we can see that there is a 37 in both sets, so we have a subset of length 1 that works, but there is no other such subset, so we can't have $\{1, 1, 4\}$. For $\{2,2,2\}$, we can see that $\{4, 51\}$ works since $4 + 51 = 55$, which is in $T$, but there are no other subsets of length 2 that work. That leaves $\{1, 2, 3\}$. We already showed that $\{37\}$ and $\{4, 51\}$ work, so let's just check that the remaining values work: $5 + 9 + 30 = 44$, which is in $T$, so that works. Thus, our final "partitioning" is $\{\{37\}, \{4, 51\}, \{5, 9, 30\}\}$.

This is fine for small values of $k$ and $m$, but using my approach it quickly blows up. Is there a better way to approach this problem?

Helpful addition: it is possible to get more sets $T_1, T_2, ...$ of length $m$ that have different values that the same values in $S$ must sum to, not sure if this is helpful or not.

Answer 1

This is an unsplittable flow problem in a bipartite network. Let $A=\{1,\dots,k\}$ be the set of supply nodes, with supply $s_i$ for node $i\in A$. Let $B=\{1,\dots,m\}$ be the set of demand nodes, with demand $d_j$ for node $j\in B$. For $i\in A$ and $j\in B$, let binary decision variable $x_{ij}$ indicate whether the supply from node $i$ is assigned to node $j$. The problem is to satisfy the following linear constraints: \begin{align} \sum_{j\in B} x_{ij} &= 1 &&\text{for all $i\in A$} \tag1\label1 \\ \sum_{i\in A} s_i x_{ij} &= d_j &&\text{for all $j\in B$} \tag2\label2 \end{align} Constraint \eqref{1} assigns supply node $i$ to exactly one demand node $j$. Constraint \eqref{2} assigns a total of $d_j$ units to demand node $j$.