0

Sorry if I'm not always using the right words, I'm not a native English speaker. I am working on an algorithm but it's just brute force at the moment and I'm a bit stuck right now...

Consider this equation with $n$ variables: $x_1 + x_2 + \ldots + x_n = 0$

We also have a set $A = \{a_1, a_2, \ldots,a_m\}$ containing $m$ possible values for $x_1 \ldots x_n$ with $m > n$ and $a_m \in \mathbb{R}$.

Any value can only be used once. Also, using the same values but in different locations is considered a distinct solution.

As an example, we have the equation $x_1 + x_2 + x_3 = 0$ and the set $A=\{-5, 0, 2, 3, 5\}$. There are obviously multiple solutions, e.g. $$\begin{eqnarray}5+0-5=0\\0+5-5=0\\2+3-5=0\end{eqnarray}$$ and so on.

For small values of $n$ and $m$ the solutions can quickly be found by checking all combinations with brute force, but I want to be able to also do this for larger values like $n = 10$, $m = 200$.

Is there an efficient method for this? I'm not using Python or other languages with special math packages, but usually code in C or J.

mattg
  • 1

1 Answers1

1

The bad news is that this is a variation on the subset sum problem, which is known to be computationally difficult to tackle as the size of the problem increases.

The good news is that there are ways to tackle the problem more efficiently than complete brute force, and in extremely large cases there are plenty of commercial and open source software packages that can do quite clever things to try to solve it.

As an example of an algorithm that will be at least a little better than complete brute force, you could build a function that recursively checks for valid subset sum solutions of given length, something like this:

Let $\operatorname{SubsetSum}(A, T, n)$ return any subsets of $A$ of size $n$ that sum to $T$. Do this by:

  1. If there are definitely no solutions (via some heuristic), return a failure message.

  2. If the problem is small enough to brute force, do that and return the result.

  3. Otherwise, find the value in $A$ with the largest absolute value, call it $M$.

  4. Call $\operatorname{SubsetSum}(A \setminus \{M\}, T - M, n - 1)$. If it found any solutions, add $M$ to them and return them as solutions.

  5. Call $\operatorname{SubsetSum}(A \setminus \{M\}, T, n)$ and return any solutions.

  6. If 4 and 5 both returned a failure message, return a failure message.

In other words, you split the problem into "Are there any solutions that include $M$?" and "Are there any solutions that exclude $M$?", noting that these questions are equivalent to solving a smaller problem.

ConMan
  • 24,300