I do not have a background in math, and am wondering what type of question this is. I looked combinatorics optimization, and the knapsack problem, but found the vocabulary too dense.
The problem: Given the following array A = [2,3,4], what is the best way to find all arrays of coefficients of A that give the product equal to 10.
Ex:
A = [2,3,4]
B = [5,0,0]
C = A * B = [10,0,0]
Sum of C = 10
All Answers: [5,0,0], [3,0,1], [2,2,0], [0,2,1] Just to restate, what is the best way to find the above answers (keeping in mind the target product could be large, like 100,000)?
If you want to find all nonnegative integer solutions, i.e.,
$$\{ (x,y,z) \in \mathbb N^3 \mid 2 x + 3 y + 4 z = 10 \}$$
then you can simply brute-force it. In Haskell,
Hence, there are $5$ nonnegative integer solutions
$$\{ (0,2,1), (1,0,2), (2,2,0), (3,0,1), (5,0,0) \}$$
A much smarter way of finding all nonnegative integer solutions is to write $x = 5 - \frac{3}{2} y - 2 z$. Let
$$y = 2 m_1 \qquad \qquad z = m_2$$
where $m_1 \in \{0,1,2\}$ and $m_2 \in \{0,1,2,3\}$. Hence, the solution set can be parametrized as follows
$$\begin{bmatrix} x\\ y\\ z\end{bmatrix} = \begin{bmatrix} 5\\ 0\\ 0\end{bmatrix} + m_1 \begin{bmatrix} -3\\ 2\\ 0\end{bmatrix} + m_2 \begin{bmatrix} -2\\ 0\\ 1\end{bmatrix}$$
In Haskell,
We obtain the same $5$ solutions, though in a different order. However, we searched over a set of cardinality $12$, rather than one of cardinality $120$, as previously.