Say I have some multiset of integers, for example $M1=\{6,6,4,4,4,2,2\}$.
I have a second multiset that consists of some set of valid sums derived from picking without replacement from $M1$, say for example $M2=\{16,8,4\}$
I'd like to count the number of ways that $M2$ can be formed from $M1$. In the simple example above, the valid picks are
$ \begin{array}{ccc} \{2,2,6,6\} & \{4,4\} & \{4\} \\ \{2,4,4,6\} & \{2,6\} & \{4\} \\ \{4,6,6\} & \{2,2,4\} & \{4\} \\ \{4,6,6\} & \{4,4\} & \{2,2\} \\ \end{array} $
So the desired result is $4$.
I'm currently doing this algorithmically by getting the integer partitions of each element in $M2$ restricted to members of $M1$, then eliminating invalid ones, then doing a cartesian product of those sets, and eliminating those that are invalid (e.g., tally of elements does not match that of $M1$).
Obviously, this gets inefficient quickly.
Is there some combinatorial structure that enumerates this kind of thing? I poked through my copy of Andrews' and searched via Google scholar and came up blank.
I suspect you could do this recursively.
So starting with $M1$, there are only two ways of getting elements to add up to $4$: $\{2,2\}$ and $\{4\}$.
From $M1\text{\\} \{2,2\}=\{6,6,4,4,4\}$ there is one way of getting elements to add up to $8$: $\{4,4\}$. From $M1\text{\\} \{2,2,4,4\}=\{6,6,4\}$ there is one way of getting elements to add up to $16$.
From $M1\text{\\} \{4\}=\{6,6,4,4,2,2\}$ there are three ways of getting elements to add up to $8$: $\{2,2,4\}$, $\{2,6\}$, $\{4,4\}$. From each of what remains there is one way of getting elements to add up to $16$.
Hence your four examples.
Just repeat doing this. You already have to deduplicate when $M1$ has repeated elements, and you may need to do so when $M2$ does. My guess is that it may be easier to take the smaller elements of $M2$ as early targets, though no doubt there are particular examples where the reverse is true.