Partitioning a set to get a sum

Question

I have a set of numbers: 2,2,4,4,4,4,4,4,6,6,6,6,6,6

I want to enumerate the possible ways to partition this set into 4 groups, each of which sum to 16.

How can I approach this short of brute force?

Answer 1

Consider the six $6$s. There are only two patterns to separate six $6$s into four groups :

$$\{6,6\},\{6,6\},\{6\},\{6\}$$ and $$\{6,6\},\{6,6\},\{6,6\},\{\}.$$

(Note that the number of $6$ in each group has to be smaller than 3.)

For the former, note that each group which has only one $6$ has to have only one $2$ so the four groups will be $$\{6,6,4\},\{6,6,4\},\{6,2,4,4\},\{6,2,4,4\}.$$ (Note that $6+4k$ cannot be $16$ for $k\in\mathbb N$.)

For the latter, you have only two patterns : $$\{6,6,2,2\},\{6,6,4\},\{6,6,4\},\{4,4,4,4\}$$ and $$\{6,6,4\},\{6,6,4\},\{6,6,4\},\{2,2,4,4,4\}.$$

(To understand this, consider $\{6,6,\star\},\{6,6,\star\},\{6,6,\star\},\{\star,\star,\star,\star\}$ where one $\star$ represents $4$. You can replace one $\star$ by $2+2$.)